强连通分量

#include <bits/stdc++.h>

const int N = 1e5 + 10;
std::vector<int> edge[N];
void add_edge(int from, int to) {
    edge[from].emplace_back(to);
}
int dfn[N], low[N], stamp = 0;
int scc_cnt = 0, scc_id[N];
std::vector<int> scc[N];
bool inst[N];
std::stack<int> st;

void dfs(int from) {
    dfn[from] = low[from] = ++ stamp;
    st.emplace(from);
    inst[from] = true;
    for (auto to : edge[from]) {
        if (dfn[to] == -1) {
            dfs(to);
            low[from] = std::min(low[from], low[to]);
        } else if (inst[to]) {
            low[from] = std::min(low[from], dfn[to]);
        }
    }
    if (dfn[from] == low[from]) {
        ++ scc_cnt;
        int now = 0;
        do {
            now = st.top();
            st.pop();
            inst[now] = false;
            scc_id[now] = scc_cnt;
            scc[scc_cnt].emplace_back(now);
        } while (now != from);  
    }
}

int main() {
    std::cin.tie(nullptr)->sync_with_stdio(false);
    int n, m;
    std::cin >> n >> m;
    for (int i = 1; i <= m; i ++) {
        int from, to;
        std::cin >> from >> to;
        add_edge(from, to);
    }
}

点双连通分量

#include <bits/stdc++.h>

const int N = 5e5 + 10;
std::vector<int> edge[N];
void add_edge(int from, int to) {
    edge[from].emplace_back(to);
    edge[to].emplace_back(from);
}

int dfn[N], low[N], stamp = 0;
bool iscut[N];
std::vector<std::vector<int>> bcc;
std::stack<int> st;

void dfs(int from, bool isroot) {
    dfn[from] = low[from] = ++ stamp;
    st.push(from);
    int cl_cnt = 0;
    if (edge[from].empty() && isroot) {
        bcc.push_back({from});
        return;
    }
    for (auto to : edge[from]) {
        if (!dfn[to]) {
            dfs(to, false);
            low[from] = std::min(low[from], low[to]);
            if (low[to] >= dfn[from]) {
                cl_cnt ++;
                if (!isroot || cl_cnt >= 2) {
                    iscut[from] = true;
                }
                int now = 0;
                bcc.push_back({});
                do {
                    now = st.top();
                    st.pop();
                    bcc.back().push_back(now);
                } while (now != to);
                bcc.back().push_back(from);
            }
        } else {
            low[from] = std::min(low[from], dfn[to]);
        }
    }
}

int main() {
    std::cin.tie(nullptr)->sync_with_stdio(false);
    int n, m;
    std::cin >> n >> m;
    for (int i = 1; i <= m; i ++) {
        int a, b;
        std::cin >> a >> b;
        if (a == b) {  // 注意判掉自环
            continue;
        }
        add_edge(a, b);
    }
    for (int i = 1; i <= n; i ++) {
        if (!dfn[i]) {
            dfs(i, true);
        }
    }
    std::cout << bcc.size() << '\n';
    for (auto &i : bcc) {
        std::cout << i.size() << ' ';
        for (auto j : i) {
            std::cout << j << ' ';
        }
        std::cout << '\n';
    }
}

边双连通分量

#include <bits/stdc++.h>

const int N = 5e5 + 10, M = 2e6 + 10;
std::vector<std::pair<int,int>> edge[N];
void add_edge(int from, int to, int id) {
    edge[from].emplace_back(to, id);
    edge[to].emplace_back(from, id);
}

int dfn[N], low[N], stamp = 0;
bool bridge[M];

void dfs(int from, int id) {
    dfn[from] = low[from] = ++ stamp;
    for (auto [to, eid] : edge[from]) {
        if (!dfn[to]) {
            dfs(to, eid);
            low[from] = std::min(low[from], low[to]);
        } else if (id != eid) {
            low[from] = std::min(low[from], dfn[to]);
        }
    }
    if (dfn[from] == low[from] && id != -1) {
        bridge[id] = true;
    }
}

std::vector<std::vector<int>> dcc;
bool vis[N];
void dfs(int from) {
    vis[from] = true;
    dcc.back().push_back(from);
    for (auto [to, id] : edge[from]) {
        if (!bridge[id] && !vis[to]) {
            dfs(to);
        }
    }
}

int main() {
    std::cin.tie(nullptr)->sync_with_stdio(false);
    int n, m;
    std::cin >> n >> m;
    for (int i = 1; i <= m; i ++) {
        int a, b;
        std::cin >> a >> b;
        add_edge(a, b, i);
    }
    for (int i = 1; i <= n; i ++) {
        if (!dfn[i]) {
            dfs(i, -1);
        }
    }
    for (int i = 1; i <= n; i ++) {
        if (!vis[i]) {
            dcc.push_back({});
            dfs(i);
        }
    }
    std::cout << dcc.size() << '\n';
    for (const auto &i : dcc) {
        std::cout << i.size() << ' ';
        for (auto j : i) {
            std::cout << j << ' ';
        }
        std::cout << '\n';
    }
}