Library

This documentation is automatically generated by competitive-verifier/competitive-verifier

View the Project on GitHub anmichi/Library

:heavy_check_mark: test/TwoEdgeConnectedComponents.test.cpp

Depends on

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 :heavy_check_mark: AC 5 ms 4 MB
g++ example_01 :heavy_check_mark: AC 4 ms 4 MB
g++ example_02 :heavy_check_mark: AC 4 ms 4 MB
g++ large_cycle_00 :heavy_check_mark: AC 71 ms 39 MB
g++ max_random_00 :heavy_check_mark: AC 143 ms 52 MB
g++ max_random_01 :heavy_check_mark: AC 146 ms 53 MB
g++ max_random_02 :heavy_check_mark: AC 147 ms 53 MB
g++ random_1_00 :heavy_check_mark: AC 91 ms 35 MB
g++ random_1_01 :heavy_check_mark: AC 105 ms 41 MB
g++ random_1_02 :heavy_check_mark: AC 51 ms 18 MB
g++ random_2_00 :heavy_check_mark: AC 25 ms 8 MB
g++ random_2_01 :heavy_check_mark: AC 9 ms 5 MB
g++ random_2_02 :heavy_check_mark: AC 34 ms 10 MB
g++ random_2_03 :heavy_check_mark: AC 45 ms 12 MB
g++ random_2_04 :heavy_check_mark: AC 21 ms 7 MB
g++ small_random_1_00 :heavy_check_mark: AC 4 ms 4 MB
g++ small_random_1_01 :heavy_check_mark: AC 4 ms 4 MB
g++ small_random_1_02 :heavy_check_mark: AC 4 ms 4 MB
g++ small_random_2_00 :heavy_check_mark: AC 4 ms 4 MB
g++ small_random_2_01 :heavy_check_mark: AC 4 ms 4 MB
g++ small_random_2_02 :heavy_check_mark: AC 4 ms 4 MB
clang++ example_00 :heavy_check_mark: AC 5 ms 4 MB
clang++ example_01 :heavy_check_mark: AC 5 ms 4 MB
clang++ example_02 :heavy_check_mark: AC 5 ms 4 MB
clang++ large_cycle_00 :heavy_check_mark: AC 88 ms 43 MB
clang++ max_random_00 :heavy_check_mark: AC 165 ms 54 MB
clang++ max_random_01 :heavy_check_mark: AC 141 ms 54 MB
clang++ max_random_02 :heavy_check_mark: AC 167 ms 54 MB
clang++ random_1_00 :heavy_check_mark: AC 95 ms 36 MB
clang++ random_1_01 :heavy_check_mark: AC 114 ms 43 MB
clang++ random_1_02 :heavy_check_mark: AC 56 ms 19 MB
clang++ random_2_00 :heavy_check_mark: AC 24 ms 8 MB
clang++ random_2_01 :heavy_check_mark: AC 9 ms 5 MB
clang++ random_2_02 :heavy_check_mark: AC 33 ms 10 MB
clang++ random_2_03 :heavy_check_mark: AC 44 ms 12 MB
clang++ random_2_04 :heavy_check_mark: AC 21 ms 8 MB
clang++ small_random_1_00 :heavy_check_mark: AC 5 ms 4 MB
clang++ small_random_1_01 :heavy_check_mark: AC 8 ms 4 MB
clang++ small_random_1_02 :heavy_check_mark: AC 5 ms 4 MB
clang++ small_random_2_00 :heavy_check_mark: AC 5 ms 4 MB
clang++ small_random_2_01 :heavy_check_mark: AC 4 ms 4 MB
clang++ small_random_2_02 :heavy_check_mark: AC 4 ms 4 MB
Back to top page