This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub knshnb/competitive_library
#define PROBLEM "https://judge.yosupo.jp/problem/two_edge_connected_components" #include <bits/stdc++.h> // clang-format off using Int = long long; #define REP_(i, a_, b_, a, b, ...) for (Int i = (a), lim##i = (b); i < lim##i; i++) #define REP(i, ...) REP_(i, __VA_ARGS__, __VA_ARGS__, 0, __VA_ARGS__) struct SetupIO { SetupIO() { std::cin.tie(nullptr), std::ios::sync_with_stdio(false), std::cout << std::fixed << std::setprecision(13); } } setup_io; #ifndef _MY_DEBUG #define dump(...) #endif // clang-format on /** * author: knshnb * created: Wed Apr 1 19:23:42 JST 2020 **/ #define CALL_FROM_TEST #include "../../src/Graph/TwoEdgeConnectedComponents.hpp" #undef CALL_FROM_TEST signed main() { Int n, m; std::cin >> n >> m; TwoEdgeConnectedComponents t(n); REP(i, m) { int u, v; std::cin >> u >> v; t.g[u].push_back(v); t.g[v].push_back(u); } t.build(); std::vector<std::vector<int>> groups(t.size); REP(i, n) { groups[t.belong_to[i]].push_back(i); } std::cout << groups.size() << std::endl; for (auto& vs : groups) { std::cout << vs.size() << " "; for (auto v : vs) std::cout << v << " "; std::cout << "\n"; } }
#line 1 "test/yosupo/two_edge_connected_components.test.cpp" #define PROBLEM "https://judge.yosupo.jp/problem/two_edge_connected_components" #include <bits/stdc++.h> // clang-format off using Int = long long; #define REP_(i, a_, b_, a, b, ...) for (Int i = (a), lim##i = (b); i < lim##i; i++) #define REP(i, ...) REP_(i, __VA_ARGS__, __VA_ARGS__, 0, __VA_ARGS__) struct SetupIO { SetupIO() { std::cin.tie(nullptr), std::ios::sync_with_stdio(false), std::cout << std::fixed << std::setprecision(13); } } setup_io; #ifndef _MY_DEBUG #define dump(...) #endif // clang-format on /** * author: knshnb * created: Wed Apr 1 19:23:42 JST 2020 **/ #define CALL_FROM_TEST #line 1 "src/Graph/TwoEdgeConnectedComponents.hpp" /// @docs src/Graph/TwoEdgeConnectedComponents.md struct TwoEdgeConnectedComponents { int n; std::vector<std::vector<int>> g; std::vector<std::pair<int, int>> bridges; // 列挙された橋 std::vector<int> belong_to; // 各頂点の属する二重辺連結成分のindex int size = -1; // 二重辺連結成分の個数 TwoEdgeConnectedComponents(int n_) : n(n_), g(n_) {} TwoEdgeConnectedComponents(const std::vector<std::vector<int>>& g_) : n(g_.size()), g(g_) {} void build() { // dfs木を作り、各辺が後退辺にはさまれているかどうかをimos法で判定 std::vector<int> imos(n); // imos[i] == 0なら(i, par)が橋になるように更新 std::vector<int> flag(n); // 0: unvisited, 1: ancestor of current v, 2: done(後退辺になりえない) auto dfs1 = [&](auto f, int v, int prv) -> void { flag[v] = 1; bool skipped_parent = false; for (int s : g[v]) { if (s == prv && !skipped_parent) { // 多重辺に対応 skipped_parent = true; continue; } if (flag[s] == 0) { f(f, s, v); if (imos[s] == 0) bridges.push_back({v, s}); imos[v] += imos[s]; } else if (flag[s] == 1) { // 後退辺 imos[v]++; imos[s]--; } } flag[v] = 2; }; for (int i = 0; i < n; i++) { if (flag[i] == 0) dfs1(dfs1, i, -1); } // 橋(imos[i] == 0となるような(i, par))で区切って二重編連結成分に分ける int cur_group = 0; belong_to.assign(n, -1); auto dfs2 = [&](auto f, int v) -> void { for (int s : g[v]) { if (belong_to[s] != -1) continue; belong_to[s] = imos[s] == 0 ? cur_group++ : belong_to[v]; f(f, s); } }; for (int i = 0; i < n; i++) { if (belong_to[i] == -1) { belong_to[i] = cur_group++; dfs2(dfs2, i); } } size = cur_group; } }; #line 19 "test/yosupo/two_edge_connected_components.test.cpp" #undef CALL_FROM_TEST signed main() { Int n, m; std::cin >> n >> m; TwoEdgeConnectedComponents t(n); REP(i, m) { int u, v; std::cin >> u >> v; t.g[u].push_back(v); t.g[v].push_back(u); } t.build(); std::vector<std::vector<int>> groups(t.size); REP(i, n) { groups[t.belong_to[i]].push_back(i); } std::cout << groups.size() << std::endl; for (auto& vs : groups) { std::cout << vs.size() << " "; for (auto v : vs) std::cout << v << " "; std::cout << "\n"; } }