python/TangDou/AcWing/DCC/YFS_1.cpp

#include <bits/stdc++.h>
using namespace std;
const int MN = 100005;

int N, M, cnt;
vector<int> G[MN], T[MN * 2];

int dfn[MN], low[MN], dfc;
int stk[MN], tp;

void Tarjan(int u) {
    printf("  Enter : #%d\n", u);
    low[u] = dfn[u] = ++dfc;              // low 初始化为当前节点 dfn
    stk[++tp] = u;                        // 加入栈中
    for (int v : G[u]) {                  // 遍历 u 的相邻节点
        if (!dfn[v]) {                    // 如果未访问过
            Tarjan(v);                    // 递归
            low[u] = min(low[u], low[v]); // 未访问的和 low 取 min
            if (low[v] == dfn[u]) {       // 标志着找到一个以 u 为根的点双连通分量
                ++cnt;                    // 增加方点个数
                printf("  Found a New BCC #%d.\n", cnt - N);
                // 将点双中除了 u 的点退栈，并在圆方树中连边
                for (int x = 0; x != v; --tp) {
                    x = stk[tp];
                    T[cnt].push_back(x);
                    T[x].push_back(cnt);
                    printf("    BCC #%d has vertex #%d\n", cnt - N, x);
                }
                // 注意 u 自身也要连边（但不退栈）
                T[cnt].push_back(u);
                T[u].push_back(cnt);
                printf("    BCC #%d has vertex #%d\n", cnt - N, u);
            }
        } else
            low[u] = min(low[u], dfn[v]); // 已访问的和 dfn 取 min
    }
    printf("  Exit : #%d : low = %d\n", u, low[u]);
    printf("  Stack:\n    ");
    for (int i = 1; i <= tp; ++i) printf("%d, ", stk[i]);
    puts("");
}

int main() {
#ifndef ONLINE_JUDGE
    freopen("YFS.in", "r", stdin);
    freopen("YFS_1.out", "w", stdout);
#endif
    scanf("%d%d", &N, &M);
    cnt = N; // 点双 / 方点标号从 N 开始
    for (int i = 1; i <= M; ++i) {
        int u, v;
        scanf("%d%d", &u, &v);
        G[u].push_back(v); // 加双向边
        G[v].push_back(u);
    }
    // 处理非连通图
    for (int u = 1; u <= N; ++u)
        if (!dfn[u]) Tarjan(u), --tp;
    // 注意到退出 Tarjan 时栈中还有一个元素即根，将其退栈
    return 0;
}