sotanishy's code snippets for competitive programming
View the Project on GitHub sotanishy/cp-library-cpp
#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_3_A" #include "../../graph/lowlink.hpp" #include <bits/stdc++.h> using namespace std; int main() { ios_base::sync_with_stdio(false); cin.tie(0); int V, E; cin >> V >> E; vector<vector<int>> G(V); for (int i = 0; i < E; ++i) { int s, t; cin >> s >> t; G[s].push_back(t); G[t].push_back(s); } Lowlink lowlink(G); auto pts = lowlink.articulation; sort(pts.begin(), pts.end()); for (int v : pts) cout << v << "\n"; }
#line 1 "test/aoj/GRL_3_A.test.cpp" #define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_3_A" #line 2 "graph/lowlink.hpp" #include <algorithm> #include <utility> #include <vector> class Lowlink { public: std::vector<int> ord, low; std::vector<std::pair<int, int>> bridge; std::vector<int> articulation; Lowlink() = default; explicit Lowlink(const std::vector<std::vector<int>>& G) : ord(G.size(), -1), low(G.size()), G(G) { for (int i = 0; i < (int)G.size(); ++i) { if (ord[i] == -1) dfs(i, -1); } } bool is_bridge(int u, int v) const { if (ord[u] > ord[v]) std::swap(u, v); return ord[u] < low[v]; } private: std::vector<std::vector<int>> G; int k = 0; void dfs(int v, int p) { ord[v] = k++; low[v] = ord[v]; bool is_articulation = false, checked = false; int cnt = 0; for (int c : G[v]) { if (c == p && !checked) { checked = true; continue; } if (ord[c] == -1) { ++cnt; dfs(c, v); low[v] = std::min(low[v], low[c]); if (p != -1 && ord[v] <= low[c]) is_articulation = true; if (ord[v] < low[c]) bridge.push_back(std::minmax(v, c)); } else { low[v] = std::min(low[v], ord[c]); } } if (p == -1 && cnt > 1) is_articulation = true; if (is_articulation) articulation.push_back(v); } }; #line 4 "test/aoj/GRL_3_A.test.cpp" #include <bits/stdc++.h> using namespace std; int main() { ios_base::sync_with_stdio(false); cin.tie(0); int V, E; cin >> V >> E; vector<vector<int>> G(V); for (int i = 0; i < E; ++i) { int s, t; cin >> s >> t; G[s].push_back(t); G[t].push_back(s); } Lowlink lowlink(G); auto pts = lowlink.articulation; sort(pts.begin(), pts.end()); for (int v : pts) cout << v << "\n"; }