Tarjan算法求割点和桥

定义：

• 割点：在一个无向连通图中，若删除某点后，图变成不连通，则称该点为该图的割点。
• 桥：在一个无向连通图中，若删除某边后，图变成不连通，则称该边为该图的桥。

Tarjan算法求割点和桥的思路同样也基于对图的DFS：

• 表示节点在DFS搜索中是第几个被搜索到的（时间戳）。
• 表示从在DFS搜索树中以节点为根的子树中节点不通过节点的父节点到节点这条边所能到达的所有节点的的最小值。

一个节点是割点，当且仅当满足下面的条件1或2：

1. 如果节点是总的DFS树的根，该节点有多于1个的子树。
2. 如果节点不是总的DFS树的根，该节点存在一颗子树，子树的根节点为，且。

一条边是桥，当且仅当边没有重边，且。

需要使用到的全局变量的定义：

int N; // N表示节点总个数
vector <int> E, cutp; // cutp存储割点
int dfn[MAXN], low[MAXN], timer;
struct Edge{int from, to;};
vector <Edge> br; // br存储桥

DFS搜索可以如下实现（参考代码）：

// 这段代码求桥时未考虑重边的情况
void dfs(int u, int fa){
    dfn[u] = low[u] = ++timer;
    int son = 0;
    bool f = false;
    for(int i=0;i<E[u].size();i++){
        int v = E[u][i];
        if(v == fa) continue;
        if(!dfn[v]){
            son++;
            dfs(v, u);
            if(dfn[u] <= low[v]) f = true;
            if(dfn[u] < low[v]) br.push_back((Edge){u, v});
            low[u] = min(low[u], low[v]);
        }
        else low[u] = min(low[u], dfn[v]);
    }
    if((!fa && son>1) || (fa && f)) cutp.push_back(u);
}

Tarjan算法只需要调用上面的dfs函数即可，代码如下：

void Tarjan(){
    for(int i=1;i<=N;i++){
        if(!dfn[i]) dfs(i, 0);
    }
}

---

附上一道练习题，链接洛谷P3388 【模板】割点（割顶）。

AC代码：

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <vector>
#include <stack>
using namespace std;
const int MAXN = 20000+10;
int N, M;
vector <int> E[MAXN], cutp;
int dfn[MAXN], low[MAXN], timer;
void dfs(int u, int fa){
    dfn[u] = low[u] = ++timer;
    int son = 0;
    bool f = false;
    for(int i=0;i<E[u].size();i++){
        int v = E[u][i];
        if(v == fa) continue;
        if(!dfn[v]){
            son++;
            dfs(v, u);
            if(dfn[u] <= low[v]) f = true;
            low[u] = min(low[u], low[v]);
        }
        else low[u] = min(low[u], dfn[v]);
    }
    if((!fa && son>1) || (fa && f)) cutp.push_back(u);
}
void Tarjan(){
    for(int i=1;i<=N;i++){
        if(!dfn[i]) dfs(i, 0);
    }
}
int main(){
    scanf("%d%d", &N, &M);
    while(M--){
        int from, to;
        scanf("%d%d", &from, &to);
        E[from].push_back(to);
        E[to].push_back(from);
    }
    Tarjan();
    printf("%d\n", (int)cutp.size());
    sort(cutp.begin(), cutp.end());
    for(int i=0;i<cutp.size();i++)
        printf(i<cutp.size()-1?"%d ":"%d\n", cutp[i]);
    return 0;
}