test/yosupo/graph/biconnected_components.test.cpp

View this file on GitHub
Last update: 2025-12-02 19:33:27+07:00
Problem: https://judge.yosupo.jp/problem/biconnected_components

Depends on

Code

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

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

#include "graph/block_cut.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 bct = block_cut(g);
    cout << bct.size() - n << "\n";
    for (int i = n; i < bct.size(); i++) {
        cout << bct[i].size();
        for (int v : bct[i]) cout << " " << v;
        cout << "\n";
    }
}

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

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

#line 2 "graph/block_cut.hpp"

#line 2 "other/y_combinator.hpp"

template<class F> struct y_comb_t : F {
    template<class T> y_comb_t(T &&_f) : F(forward<T>(_f)) {}
    template<class... Args> decltype(auto) operator()(Args &&...args) {
        return F::operator()(/* ref */(*this), forward<Args>(args)...);
    }
};
template<class F> y_comb_t<decay_t<F>> y_comb(F &&f) { return {forward<F>(f)}; }
#line 4 "graph/block_cut.hpp"

// https://x.com/noshi91/status/1529858538650374144
// https://maspypy.github.io/library/graph/block_cut.hpp
// [0, n): original vertices, [n, n_block): BCC representative
// if v in C then there is an edge (v, id(C))
// cut points are vertices v in [0, n) with deg(v) >= 2
template<class G> auto block_cut(const G &g) {
    const int n = (int)g.size();

    vector<int> in(n), low(n), st;
    vector<bool> vis(n);
    vector<basic_string<int>> bct(2 * n);
    st.reserve(n);
    auto add_edge = [&](int u, int v) { bct[u] += v, bct[v] += u; };

    int comp = n, time = 0;
    auto dfs = y_comb([&](auto &self, int v, int p) -> void {
        st.push_back(v), vis[v] = true;
        in[v] = low[v] = time++;
        int cnt = 0;
        for (int c : g[v]) {
            if (c == p) continue;
            if (!vis[c]) {
                cnt++;
                int s = (int)st.size();
                self(c, v);
                low[v] = min(low[v], low[c]);
                if ((p == -1 && cnt > 1) || (p != -1 && low[c] >= in[v])) {
                    add_edge(comp, v);
                    for (; st.size() > s; st.pop_back())
                        add_edge(comp, st.back());
                    comp++;
                }
            } else {
                low[v] = min(low[v], in[c]);
            }
        }
    });

    for (int i = 0; i < n; i++) {
        if (vis[i]) continue;
        dfs(i, -1);
        for (int v : st) add_edge(comp, v);
        comp++, st.clear();
    }
    bct.resize(comp), bct.shrink_to_fit();
    return bct;
}
#line 7 "test/yosupo/graph/biconnected_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 bct = block_cut(g);
    cout << bct.size() - n << "\n";
    for (int i = n; i < bct.size(); i++) {
        cout << bct[i].size();
        for (int v : bct[i]) 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	281 ms	149 MB
g++	max_line_clique_00	AC	199 ms	76 MB
g++	max_random_00	AC	265 ms	104 MB
g++	max_random_2_00	AC	248 ms	84 MB
g++	max_random_2_01	AC	243 ms	84 MB
g++	max_random_2_02	AC	239 ms	83 MB
g++	max_star_00	AC	228 ms	90 MB
g++	max_tree_00	AC	268 ms	91 MB
g++	min_00	AC	5 ms	4 MB
g++	min_01	AC	4 ms	4 MB
g++	min_02	AC	4 ms	4 MB
g++	random_1_00	AC	212 ms	83 MB
g++	random_2_00	AC	218 ms	75 MB
g++	random_2_01	AC	132 ms	79 MB
g++	random_2_02	AC	103 ms	29 MB
g++	small_random_1_00	AC	6 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	308 ms	141 MB
clang++	max_line_clique_00	AC	176 ms	73 MB
clang++	max_random_00	AC	264 ms	101 MB
clang++	max_random_2_00	AC	242 ms	84 MB
clang++	max_random_2_01	AC	262 ms	84 MB
clang++	max_random_2_02	AC	232 ms	83 MB
clang++	max_star_00	AC	243 ms	89 MB
clang++	max_tree_00	AC	339 ms	91 MB
clang++	min_00	AC	6 ms	4 MB
clang++	min_01	AC	4 ms	4 MB
clang++	min_02	AC	4 ms	4 MB
clang++	random_1_00	AC	190 ms	81 MB
clang++	random_2_00	AC	196 ms	75 MB
clang++	random_2_01	AC	130 ms	79 MB
clang++	random_2_02	AC	103 ms	29 MB
clang++	small_random_1_00	AC	5 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