test/yosupo/graph/two_edge_connected_components.test.cpp

• View this file on GitHub
• Last update: 2025-09-20 17:47:50+07:00
• Problem: https://judge.yosupo.jp/problem/two_edge_connected_components

Depends on

• Bridge Tree (graph/bridge_tree.hpp)

Code

#define PROBLEM "https://judge.yosupo.jp/problem/two_edge_connected_components"

#include <bits/stdc++.h>
using namespace std;

#include "graph/bridge_tree.hpp"

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    int n, m;
    cin >> n >> m;
    vector<basic_string<int>> g(n);
    for (int i = 0, u, v; i < m; i++) {
        cin >> u >> v;
        g[u] += v, g[v] += u;
    }

    auto id = two_cc(g);
    int k = *max_element(begin(id), end(id)) + 1;
    vector<basic_string<int>> ccs(k);
    for (int i = 0; i < n; i++) ccs[id[i]] += i;
    cout << ccs.size() << "\n";
    for (auto cc : ccs) {
        cout << cc.size();
        for (int v : cc) cout << " " << v;
        cout << "\n";
    }
}

#line 1 "test/yosupo/graph/two_edge_connected_components.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/two_edge_connected_components"

#include <bits/stdc++.h>
using namespace std;

#line 2 "graph/bridge_tree.hpp"

template<class G> auto two_cc(const G &g) {
    const int n = (int)g.size();
    int time = 0;
    vector<int> in(n, n), low(n);

    auto dfs = [&](auto &dfs, int v, int p) -> void {
        in[v] = low[v] = time++;
        bool skip = true;
        for (int c : g[v]) {
            if (c == p && exchange(skip, 0)) continue;
            if (in[c] < n) {
                low[v] = min(low[v], in[c]);
                continue;
            }
            dfs(dfs, c, v);
            low[v] = min(low[v], low[c]);
        }
    };
    for (int i = 0; i < n; i++)
        if (in[i] == n) dfs(dfs, i, -1);

    auto is_bridge = [&](int u, int v) {
        if (in[u] > in[v]) swap(u, v);
        return low[v] > in[u];
    };

    int k = 0;
    vector<int> id(n, n);
    queue<int> q;
    for (int i = 0; i < n; i++) {
        if (id[i] != n) continue;
        assert(q.empty());
        id[i] = k, q.push(i);
        while (q.size()) {
            int v = q.front();
            q.pop();
            for (int u : g[v]) {
                if (id[u] != n || is_bridge(u, v)) continue;
                id[u] = k;
                q.push(u);
            }
        }
        k++;
    }

    return id;
}
template<class G> auto bridge_tree(const G &g) {
    auto id = two_cc(g);
    const int n = (int)g.size(), k = *max_element(begin(id), end(id)) + 1;
    vector<basic_string<int>> ccs(k), tr(k);
    for (int v = 0; v < n; v++) {
        ccs[id[v]] += (v);
        for (int u : g[v])
            if (id[v] != id[u]) tr[id[v]] += u, tr[id[u]] += v;
    }
    for (auto &a : tr) {
        sort(begin(a), end(a));
        a.resize(unique(begin(a), end(a)) - begin(a));
    }
    return tuple(ccs, id, tr);
}
#line 7 "test/yosupo/graph/two_edge_connected_components.test.cpp"

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    int n, m;
    cin >> n >> m;
    vector<basic_string<int>> g(n);
    for (int i = 0, u, v; i < m; i++) {
        cin >> u >> v;
        g[u] += v, g[v] += u;
    }

    auto id = two_cc(g);
    int k = *max_element(begin(id), end(id)) + 1;
    vector<basic_string<int>> ccs(k);
    for (int i = 0; i < n; i++) ccs[id[i]] += i;
    cout << ccs.size() << "\n";
    for (auto cc : ccs) {
        cout << cc.size();
        for (int v : cc) 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	38 ms	14 MB
g++	max_random_00	AC	74 ms	19 MB
g++	max_random_01	AC	72 ms	19 MB
g++	max_random_02	AC	73 ms	19 MB
g++	random_1_00	AC	52 ms	13 MB
g++	random_1_01	AC	54 ms	15 MB
g++	random_1_02	AC	35 ms	9 MB
g++	random_2_00	AC	19 ms	6 MB
g++	random_2_01	AC	8 ms	4 MB
g++	random_2_02	AC	27 ms	6 MB
g++	random_2_03	AC	35 ms	7 MB
g++	random_2_04	AC	17 ms	5 MB
g++	small_random_1_00	AC	5 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	4 ms	4 MB
clang++	example_02	AC	4 ms	4 MB
clang++	large_cycle_00	AC	40 ms	18 MB
clang++	max_random_00	AC	74 ms	20 MB
clang++	max_random_01	AC	73 ms	20 MB
clang++	max_random_02	AC	73 ms	20 MB
clang++	random_1_00	AC	52 ms	15 MB
clang++	random_1_01	AC	54 ms	16 MB
clang++	random_1_02	AC	35 ms	10 MB
clang++	random_2_00	AC	19 ms	6 MB
clang++	random_2_01	AC	8 ms	4 MB
clang++	random_2_02	AC	26 ms	7 MB
clang++	random_2_03	AC	35 ms	8 MB
clang++	random_2_04	AC	16 ms	5 MB
clang++	small_random_1_00	AC	5 ms	4 MB
clang++	small_random_1_01	AC	4 ms	4 MB
clang++	small_random_1_02	AC	4 ms	4 MB
clang++	small_random_2_00	AC	4 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