【模板】边双连通分量(Edge Biconnected Components) 题解

思路分析

按题目要求使用对应数据结构与算法模拟/递推求解，注意数据范围边界与时间复杂度。

参考代码

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    if (!(cin >> n >> m)) return 0;
    vector<int> head(n + 1, -1), to(2 * m), nxt(2 * m);
    int ecnt = 0;
    auto add_edge = [&](int u, int v) {
        to[ecnt] = v;
        nxt[ecnt] = head[u];
        head[u] = ecnt++;
    };
    for (int i = 0; i < m; ++i) {
        int u, v;
        cin >> u >> v;
        if (u == v) continue;
        add_edge(u, v);
        add_edge(v, u);
    }

    vector<int> dfn(n + 1, 0), low(n + 1, 0), stk;
    int timer = 0;
    vector<vector<int>> comps;

    struct Frame { int u, in_edge, e; };
    vector<Frame> call_stk;
    for (int i = 1; i <= n; ++i) {
        if (dfn[i]) continue;
        dfn[i] = low[i] = ++timer;
        stk.push_back(i);
        call_stk.push_back({i, -1, head[i]});
        while (!call_stk.empty()) {
            auto& fr = call_stk.back();
            int u = fr.u;
            int e = fr.e;
            if (e != -1) {
                fr.e = nxt[e];
                if ((e ^ 1) == fr.in_edge) continue;
                int v = to[e];
                if (!dfn[v]) {
                    dfn[v] = low[v] = ++timer;
                    stk.push_back(v);
                    call_stk.push_back({v, e, head[v]});
                } else {
                    low[u] = min(low[u], dfn[v]);
                }
            } else {
                call_stk.pop_back();
                if (!call_stk.empty()) {
                    int p = call_stk.back().u;
                    low[p] = min(low[p], low[u]);
                }
                if (low[u] == dfn[u]) {
                    vector<int> c;
                    while (true) {
                        int x = stk.back();
                        stk.pop_back();
                        c.push_back(x);
                        if (x == u) break;
                    }
                    comps.push_back(move(c));
                }
            }
        }
    }

    cout << comps.size() << "\n";
    for (const auto& c : comps) {
        cout << c.size();
        for (int x : c) cout << ' ' << x;
        cout << "\n";
    }
    return 0;
}