This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub dnx04/algo
#define PROBLEM "https://judge.yosupo.jp/problem/two_edge_connected_components" #include <bits/stdc++.h> using namespace std; using ll = long long; #include "../lowlink.hpp" void solve(int ith) { int n, m; cin >> n >> m; lowlink t(n); for (int i = 0; i < m; ++i) { int u, v; cin >> u >> v; t.add_edge(u, v); } auto comps = t.two_edge_connected_components(); cout << comps.size() << '\n'; for (auto c : comps) { cout << c.size() << ' '; for (auto v : c) cout << v << ' '; cout << '\n'; } } signed main() { ios::sync_with_stdio(false); cin.tie(nullptr), cin.exceptions(cin.failbit); int tc = 1; // cin >> tc; for (int i = 1; i <= tc; ++i) solve(i); }
#line 1 "graph/test/Two-Edge-Connected_Components.test.cpp" #define PROBLEM "https://judge.yosupo.jp/problem/two_edge_connected_components" #include <bits/stdc++.h> using namespace std; using ll = long long; #line 1 "graph/lowlink.hpp" struct lowlink { int V; // # of vertices int E; // # of edges int k; vector<vector<pair<int, int>>> to; vector<pair<int, int>> edges; vector<int> root_ids; vector<int> is_bridge; // Whether edge i is bridge or not, size = E vector<int> is_articulation; // whether vertex i is articulation point // or not, size = V // low_link vector<int> order; vector<int> low_link; vector<int> is_dfstree_edge; int tecc_num; vector<int> tecc_id; int tvcc_num; vector<int> tvcc_id; lowlink(int V) : V(V), E(0), k(0), to(V), is_articulation(V, 0), order(V, -1), low_link(V, -1), tecc_num(0), tvcc_num(0) {} void add_edge(int v1, int v2) { assert(v1 >= 0 and v1 < V); assert(v2 >= 0 and v2 < V); to[v1].emplace_back(v2, E); to[v2].emplace_back(v1, E); edges.emplace_back(v1, v2); is_bridge.push_back(0); is_dfstree_edge.push_back(0); tvcc_id.push_back(-1); E++; } vector<int> edge_stack; int root_now; // Build DFS tree // Complexity: O(V + E) void dfs_lowlink(int now, int prv_eid = -1) { if (prv_eid < 0) root_now = k; if (prv_eid == -1) root_ids.push_back(now); order[now] = low_link[now] = k++; for (const auto &nxt : to[now]) { if (nxt.second == prv_eid) continue; if (order[nxt.first] < order[now]) edge_stack.push_back(nxt.second); if (order[nxt.first] >= 0) { low_link[now] = min(low_link[now], order[nxt.first]); } else { is_dfstree_edge[nxt.second] = 1; dfs_lowlink(nxt.first, nxt.second); low_link[now] = min(low_link[now], low_link[nxt.first]); if ((order[now] == root_now and order[nxt.first] != root_now + 1) or (order[now] != root_now and low_link[nxt.first] >= order[now])) { is_articulation[now] = 1; } if (low_link[nxt.first] >= order[now]) { while (true) { int e = edge_stack.back(); tvcc_id[e] = tvcc_num; edge_stack.pop_back(); if (e == nxt.second) break; } tvcc_num++; } } } } void build() { for (int v = 0; v < V; ++v) { if (order[v] < 0) dfs_lowlink(v); } // Find all bridges // Complexity: O(V + E) for (int i = 0; i < E; i++) { int v1 = edges[i].first, v2 = edges[i].second; if (order[v1] > order[v2]) swap(v1, v2); is_bridge[i] = order[v1] < low_link[v2]; } } // Find two-edge-connected components and classify all vertices // Complexity: O(V + E) vector<vector<int>> two_edge_connected_components() { build(); tecc_num = 0; tecc_id.assign(V, -1); vector<int> st; for (int i = 0; i < V; i++) { if (tecc_id[i] != -1) continue; tecc_id[i] = tecc_num; st.push_back(i); while (!st.empty()) { int now = st.back(); st.pop_back(); for (const auto &edge : to[now]) { int nxt = edge.first; if (tecc_id[nxt] >= 0 or is_bridge[edge.second]) continue; tecc_id[nxt] = tecc_num; st.push_back(nxt); } } ++tecc_num; } vector<vector<int>> ret(tecc_num); for (int i = 0; i < V; ++i) ret[tecc_id[i]].push_back(i); return ret; } // Find biconnected components and enumerate vertices for each component. // Complexity: O(V \log V + E) vector<vector<int>> biconnected_components_by_vertices() { build(); vector<vector<int>> ret(tvcc_num); for (int i = 0; i < E; ++i) { ret[tvcc_id[i]].push_back(edges[i].first); ret[tvcc_id[i]].push_back(edges[i].second); } for (auto &vec : ret) { sort(vec.begin(), vec.end()); vec.erase(unique(vec.begin(), vec.end()), vec.end()); } for (int i = 0; i < V; ++i) { if (to[i].empty()) ret.push_back({i}); } return ret; } // Find biconnected components and classify all edges // Complexity: O(V + E) vector<vector<int>> biconnected_components_by_edges() { build(); vector<vector<int>> ret(tvcc_num); for (int i = 0; i < E; ++i) ret[tvcc_id[i]].push_back(i); return ret; } }; #line 10 "graph/test/Two-Edge-Connected_Components.test.cpp" void solve(int ith) { int n, m; cin >> n >> m; lowlink t(n); for (int i = 0; i < m; ++i) { int u, v; cin >> u >> v; t.add_edge(u, v); } auto comps = t.two_edge_connected_components(); cout << comps.size() << '\n'; for (auto c : comps) { cout << c.size() << ' '; for (auto v : c) cout << v << ' '; cout << '\n'; } } signed main() { ios::sync_with_stdio(false); cin.tie(nullptr), cin.exceptions(cin.failbit); int tc = 1; // cin >> tc; for (int i = 1; i <= tc; ++i) solve(i); }