图论

点双连通分量

#include <bits/stdc++.h>
#define sz(a) int((a).size())
#define FOR(i, l, r) for(int i = l; i <= r; i++)
#define ROF(i, r, l) for(int i = r; i >= l; i--)
#define ll long long
#define x first
#define y second
#define pi pair<int, int>
using namespace std;
const int N = 5e5 + 10;
int n, m;
vector<int> g[N];
int dfn[N], low[N], dfncnt = 0, stk[N], top = 0;
int ver[N * 2], vertot = 0, fir[N], firtot = 0;
void tarjan(int u) {
    dfn[u] = low[u] = ++dfncnt;
    stk[++top] = u;
    for(auto v : g[u]) {
        if(!dfn[v]) {
            tarjan(v);
            low[u] = min(low[u], low[v]);
            if(low[v] >= dfn[u]) {
                fir[++firtot] = vertot;
                for(int x = -1; x != v; ) {
                    x = stk[top--];
                    ver[++vertot] = x;
                }
                ver[++vertot] = u;
            }
        } else low[u] = min(low[u], dfn[v]);
    }
}
int main() {
    cin >> n >> m;
    FOR(i, 1, m) {
        int u, v;
        cin >> u >> v;
        g[u].emplace_back(v);
        g[v].emplace_back(u);
    }
    FOR(u, 1, n) {
        int preid = vertot;
        if(!dfn[u]) {
            tarjan(u);
            top--;
            if(preid == vertot) {
                fir[++firtot] = vertot;
                ver[++vertot] = u;
            }
        }
    }
    cout << firtot << "\n";
    fir[++firtot] = vertot;
    FOR(i, 1, firtot - 1) {
        cout << fir[i + 1] - fir[i] <<" ";
        for(int j = fir[i] + 1; j <= fir[i + 1]; j++) cout << ver[j] <<" ";
        cout << "\n";
    }
    return 0;
}

边双连通分量

#include <bits/stdc++.h>
#define sz(a) int((a).size())
#define FOR(i, l, r) for(int i = l; i <= r; i++)
#define ROF(i, r, l) for(int i = r; i >= l; i--)
#define ll long long
#define x first
#define y second
#define pi pair<int, int>
using namespace std;
const int N = 5e5 + 10, M = 2e6 + 10;
struct Edge {
    int to, nxt, vis;
}e[M << 1];
int head[N], etot = 1;
int n, m;
int dfn[N], low[N], dfncnt = 0, stk[N], top = 0;
int idtot = 0;
vector<int> id[N];
void adde(int u, int v) {
    e[++etot] = Edge{v, head[u], 0}, head[u] = etot;
}
void tarjan(int u, int fa) {
    dfn[u] = low[u] = ++dfncnt;
    stk[++top] = u;
    for(int i = head[u]; i; i = e[i].nxt) {
        if(e[i].vis) continue;
        int v = e[i].to;
        e[i].vis = e[i ^ 1].vis = 1;
        if(!dfn[v]) {
            tarjan(v, u);
            low[u] = min(low[u], low[v]);
        } else low[u] = min(low[u], dfn[v]);
    }
    if(dfn[u] == low[u]) {
        idtot++;
        for(int x = -1; x != u; ) {
            x = stk[top--];
            id[idtot].emplace_back(x);
        }
    }
    return;
}
int main() {
    cin >> n >> m;
    FOR(i, 1, m) {
        int u, v;
        cin >> u >> v;
        adde(u, v), adde(v, u);
    }
    FOR(u, 1, n) if(!dfn[u]) tarjan(u, 0);
    cout << idtot << "\n";
    FOR(i, 1, idtot) {
        cout << sz(id[i]) <<" ";
        for(auto x : id[i]) cout << x <<" ";
        cout << "\n"; 
    }
    return 0;
}