This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub ngthanhtrung23/ACM_Notebook_new
#define PROBLEM "https://judge.yosupo.jp/problem/two_edge_connected_components" #include <bits/stdc++.h> using namespace std; #include "../DfsTree/BridgeArticulation.h" #define REP(i, a) for (int i = 0, _##i = (a); i < _##i; ++i) #define SZ(x) ((int)(x).size()) void dfs(int u, const vector<vector<int>>& g, const set<pair<int,int>>& bridges, vector<int>& comp, vector<bool>& visited) { visited[u] = true; comp.push_back(u); for (int v : g[u]) { if (visited[v]) continue; if (bridges.count({v, u}) || bridges.count({u, v})) continue; dfs(v, g, bridges, comp, visited); } } int32_t main() { ios::sync_with_stdio(0); cin.tie(0); int n, m; cin >> n >> m; // read edges vector<vector<int>> g(n); REP(eid,m) { int u, v; cin >> u >> v; g[u].push_back(v); g[v].push_back(u); } UndirectedDfs tree(g); set<pair<int,int>> bridges(tree.bridges.begin(), tree.bridges.end()); vector<bool> visited(n, false); vector<vector<int>> components; REP(i,n) { if (!visited[i]) { vector<int> comp; dfs(i, g, bridges, comp, visited); components.push_back(comp); } } cout << SZ(components) << endl; for (auto&& comp : components) { cout << SZ(comp); for (int x : comp) cout << ' ' << x; cout << endl; } return 0; }
#line 1 "Graph/tests/bridge_biconnected.test.cpp" #define PROBLEM "https://judge.yosupo.jp/problem/two_edge_connected_components" #include <bits/stdc++.h> using namespace std; #line 1 "Graph/DfsTree/BridgeArticulation.h" // UndirectedDFS, for finding bridges & articulation points {{{ // Assume already have undirected graph vector< vector<int> > G with V vertices // Vertex index from 0 // Usage: // UndirectedDfs tree; // Then you can use tree.bridges and tree.articulation_points // // Tested: // - https://judge.yosupo.jp/problem/two_edge_connected_components struct UndirectedDfs { vector<vector<int>> g; int n; vector<int> low, num, parent; vector<bool> is_articulation; int counter, root, children; vector< pair<int,int> > bridges; vector<int> articulation_points; map<pair<int,int>, int> cnt_edges; UndirectedDfs(const vector<vector<int>>& _g) : g(_g), n(g.size()), low(n, 0), num(n, -1), parent(n, 0), is_articulation(n, false), counter(0), children(0) { for (int u = 0; u < n; u++) { for (int v : g[u]) { cnt_edges[{u, v}] += 1; } } for(int i = 0; i < n; ++i) if (num[i] == -1) { root = i; children = 0; dfs(i); is_articulation[root] = (children > 1); } for(int i = 0; i < n; ++i) if (is_articulation[i]) articulation_points.push_back(i); } private: void dfs(int u) { low[u] = num[u] = counter++; for (int v : g[u]) { if (num[v] == -1) { parent[v] = u; if (u == root) children++; dfs(v); if (low[v] >= num[u]) is_articulation[u] = true; if (low[v] > num[u]) { if (cnt_edges[{u, v}] == 1) { bridges.push_back(make_pair(u, v)); } } low[u] = min(low[u], low[v]); } else if (v != parent[u]) low[u] = min(low[u], num[v]); } } }; // }}} #line 7 "Graph/tests/bridge_biconnected.test.cpp" #define REP(i, a) for (int i = 0, _##i = (a); i < _##i; ++i) #define SZ(x) ((int)(x).size()) void dfs(int u, const vector<vector<int>>& g, const set<pair<int,int>>& bridges, vector<int>& comp, vector<bool>& visited) { visited[u] = true; comp.push_back(u); for (int v : g[u]) { if (visited[v]) continue; if (bridges.count({v, u}) || bridges.count({u, v})) continue; dfs(v, g, bridges, comp, visited); } } int32_t main() { ios::sync_with_stdio(0); cin.tie(0); int n, m; cin >> n >> m; // read edges vector<vector<int>> g(n); REP(eid,m) { int u, v; cin >> u >> v; g[u].push_back(v); g[v].push_back(u); } UndirectedDfs tree(g); set<pair<int,int>> bridges(tree.bridges.begin(), tree.bridges.end()); vector<bool> visited(n, false); vector<vector<int>> components; REP(i,n) { if (!visited[i]) { vector<int> comp; dfs(i, g, bridges, comp, visited); components.push_back(comp); } } cout << SZ(components) << endl; for (auto&& comp : components) { cout << SZ(comp); for (int x : comp) cout << ' ' << x; cout << endl; } return 0; }