test/TwoEdgeConnectedComponents.test.cpp

• View this file on GitHub
• Last update: 2025-07-04 15:57:54+09:00
• Problem: https://judge.yosupo.jp/problem/two_edge_connected_components

Depends on

• TwoEdgeConnectedComponents.cpp

Code

// 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";
    }
}

Test cases

Env	Name	Status	Elapsed	Memory
g++	example_00	AC	5 ms	4 MB
g++	example_01	AC	4 ms	4 MB
g++	example_02	AC	4 ms	4 MB
g++	large_cycle_00	AC	71 ms	39 MB
g++	max_random_00	AC	143 ms	52 MB
g++	max_random_01	AC	146 ms	53 MB
g++	max_random_02	AC	147 ms	53 MB
g++	random_1_00	AC	91 ms	35 MB
g++	random_1_01	AC	105 ms	41 MB
g++	random_1_02	AC	51 ms	18 MB
g++	random_2_00	AC	25 ms	8 MB
g++	random_2_01	AC	9 ms	5 MB
g++	random_2_02	AC	34 ms	10 MB
g++	random_2_03	AC	45 ms	12 MB
g++	random_2_04	AC	21 ms	7 MB
g++	small_random_1_00	AC	4 ms	4 MB
g++	small_random_1_01	AC	4 ms	4 MB
g++	small_random_1_02	AC	4 ms	4 MB
g++	small_random_2_00	AC	4 ms	4 MB
g++	small_random_2_01	AC	4 ms	4 MB
g++	small_random_2_02	AC	4 ms	4 MB
clang++	example_00	AC	5 ms	4 MB
clang++	example_01	AC	5 ms	4 MB
clang++	example_02	AC	5 ms	4 MB
clang++	large_cycle_00	AC	88 ms	43 MB
clang++	max_random_00	AC	165 ms	54 MB
clang++	max_random_01	AC	141 ms	54 MB
clang++	max_random_02	AC	167 ms	54 MB
clang++	random_1_00	AC	95 ms	36 MB
clang++	random_1_01	AC	114 ms	43 MB
clang++	random_1_02	AC	56 ms	19 MB
clang++	random_2_00	AC	24 ms	8 MB
clang++	random_2_01	AC	9 ms	5 MB
clang++	random_2_02	AC	33 ms	10 MB
clang++	random_2_03	AC	44 ms	12 MB
clang++	random_2_04	AC	21 ms	8 MB
clang++	small_random_1_00	AC	5 ms	4 MB
clang++	small_random_1_01	AC	8 ms	4 MB
clang++	small_random_1_02	AC	5 ms	4 MB
clang++	small_random_2_00	AC	5 ms	4 MB
clang++	small_random_2_01	AC	4 ms	4 MB
clang++	small_random_2_02	AC	4 ms	4 MB

Back to top page