Tarjan算法求割点

int h[], e[], ne[], idx;  // 邻接表
int dfn[], low[], timestamp;
bool cut[];  // 判断一个点是否为割点
int rt;  // 根节点

// tarjan算法求割点
void tarjan(int u) {  
    // 进入u时，先标记时间戳
    dfn[u] = low[u] = ++ timestamp;
    int son = 0;
    
    for (int i = h[u]; ~i; i = ne[i]) {
        int j = e[i];  // 取出
        if (!dfn[j]) {  // 如果j尚未访问
            tarjan(j);
            // 返回时更新low，判割点
            low[u] = min(low[u], low[j]);
            if (low[j] >= dfn[u]) {
                son ++ ;  // 子树个数
                if (u != rt || son > 1) {  //判断割点条件
                    cut[u] = true;
                }
            }
        } else {  // 如果j已访问
            low[u] = min(low[u], dfn[j]);
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28