This documentation is automatically generated by competitive-verifier/competitive-verifier
// competitive-verifier: PROBLEM https://judge.yosupo.jp/problem/two_edge_connected_components
#include "../TwoEdgeConnectedComponents.cpp"
int main() {
cin.tie(0);
ios::sync_with_stdio(false);
int n, m;
cin >> n >> m;
vector<vector<int>> g(n);
rep(i, m) {
int u, v;
cin >> u >> v;
g[u].push_back(v);
g[v].push_back(u);
}
TwoEdgeConnectedComponents G(g);
auto components = G.components();
cout << components.size() << endl;
for (auto vec : components) {
cout << vec.size();
for (auto v : vec) cout << " " << v;
cout << "\n";
}
}
#line 1 "test/TwoEdgeConnectedComponents.test.cpp"
// competitive-verifier: PROBLEM https://judge.yosupo.jp/problem/two_edge_connected_components
#line 1 "TwoEdgeConnectedComponents.cpp"
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < n; i++)
struct TwoEdgeConnectedComponents {
int V;
vector<vector<int>> g, new_g;
vector<int> depth, imos, comp;
vector<vector<int>> comps;
TwoEdgeConnectedComponents(vector<vector<int>> g_) : V((int)g_.size()), g(g_), depth(V, -1), imos(V), comp(V, -1) {
int t = -1;
rep(i, V) {
if (depth[i] == -1) {
depth[i] = 0;
dfs_init(i);
comp[i] = ++t;
comps.push_back({});
new_g.push_back({});
dfs(i, t);
}
}
}
void dfs_init(int v) {
for (int u : g[v]) {
if (depth[u] == -1) {
depth[u] = depth[v] + 1;
dfs_init(u);
imos[v] += imos[u];
} else if (depth[u] < depth[v])
imos[u]--, imos[v]++;
}
}
void dfs(int v, int &t) {
comps[comp[v]].push_back(v);
for (int u : g[v]) {
if (depth[u] == depth[v] + 1 && comp[u] == -1) {
if (imos[u] <= 1) {
comp[u] = ++t;
comps.push_back({});
new_g.push_back({});
new_g[comp[v]].push_back(comp[u]);
} else
comp[u] = comp[v];
dfs(u, t);
}
}
}
vector<vector<int>> components() { return comps; }
vector<vector<int>> directed_forest() { return new_g; }
};
#line 3 "test/TwoEdgeConnectedComponents.test.cpp"
int main() {
cin.tie(0);
ios::sync_with_stdio(false);
int n, m;
cin >> n >> m;
vector<vector<int>> g(n);
rep(i, m) {
int u, v;
cin >> u >> v;
g[u].push_back(v);
g[v].push_back(u);
}
TwoEdgeConnectedComponents G(g);
auto components = G.components();
cout << components.size() << endl;
for (auto vec : components) {
cout << vec.size();
for (auto v : vec) cout << " " << v;
cout << "\n";
}
}
Env | Name | Status | Elapsed | Memory |
---|---|---|---|---|
g++ | example_00 |
![]() |
5 ms | 4 MB |
g++ | example_01 |
![]() |
4 ms | 4 MB |
g++ | example_02 |
![]() |
4 ms | 4 MB |
g++ | large_cycle_00 |
![]() |
71 ms | 39 MB |
g++ | max_random_00 |
![]() |
143 ms | 52 MB |
g++ | max_random_01 |
![]() |
146 ms | 53 MB |
g++ | max_random_02 |
![]() |
147 ms | 53 MB |
g++ | random_1_00 |
![]() |
91 ms | 35 MB |
g++ | random_1_01 |
![]() |
105 ms | 41 MB |
g++ | random_1_02 |
![]() |
51 ms | 18 MB |
g++ | random_2_00 |
![]() |
25 ms | 8 MB |
g++ | random_2_01 |
![]() |
9 ms | 5 MB |
g++ | random_2_02 |
![]() |
34 ms | 10 MB |
g++ | random_2_03 |
![]() |
45 ms | 12 MB |
g++ | random_2_04 |
![]() |
21 ms | 7 MB |
g++ | small_random_1_00 |
![]() |
4 ms | 4 MB |
g++ | small_random_1_01 |
![]() |
4 ms | 4 MB |
g++ | small_random_1_02 |
![]() |
4 ms | 4 MB |
g++ | small_random_2_00 |
![]() |
4 ms | 4 MB |
g++ | small_random_2_01 |
![]() |
4 ms | 4 MB |
g++ | small_random_2_02 |
![]() |
4 ms | 4 MB |
clang++ | example_00 |
![]() |
5 ms | 4 MB |
clang++ | example_01 |
![]() |
5 ms | 4 MB |
clang++ | example_02 |
![]() |
5 ms | 4 MB |
clang++ | large_cycle_00 |
![]() |
88 ms | 43 MB |
clang++ | max_random_00 |
![]() |
165 ms | 54 MB |
clang++ | max_random_01 |
![]() |
141 ms | 54 MB |
clang++ | max_random_02 |
![]() |
167 ms | 54 MB |
clang++ | random_1_00 |
![]() |
95 ms | 36 MB |
clang++ | random_1_01 |
![]() |
114 ms | 43 MB |
clang++ | random_1_02 |
![]() |
56 ms | 19 MB |
clang++ | random_2_00 |
![]() |
24 ms | 8 MB |
clang++ | random_2_01 |
![]() |
9 ms | 5 MB |
clang++ | random_2_02 |
![]() |
33 ms | 10 MB |
clang++ | random_2_03 |
![]() |
44 ms | 12 MB |
clang++ | random_2_04 |
![]() |
21 ms | 8 MB |
clang++ | small_random_1_00 |
![]() |
5 ms | 4 MB |
clang++ | small_random_1_01 |
![]() |
8 ms | 4 MB |
clang++ | small_random_1_02 |
![]() |
5 ms | 4 MB |
clang++ | small_random_2_00 |
![]() |
5 ms | 4 MB |
clang++ | small_random_2_01 |
![]() |
4 ms | 4 MB |
clang++ | small_random_2_02 |
![]() |
4 ms | 4 MB |