定義：

• 割點(diǎn)：在一個(gè)無向連通圖中，若刪除某點(diǎn)后，圖變成不連通，則稱該點(diǎn)為該圖的割點(diǎn)。
• 橋：在一個(gè)無向連通圖中，若刪除某邊后，圖變成不連通，則稱該邊為該圖的橋。

Tarjan算法求割點(diǎn)和橋的思路同樣也基于對圖的DFS：

• 表示節(jié)點(diǎn)在DFS搜索中是第幾個(gè)被搜索到的（時(shí)間戳）。
• 表示從在DFS搜索樹中以節(jié)點(diǎn)為根的子樹中節(jié)點(diǎn)不通過節(jié)點(diǎn)的父節(jié)點(diǎn)到節(jié)點(diǎn)這條邊所能到達(dá)的所有節(jié)點(diǎn)的的最小值。

一個(gè)節(jié)點(diǎn)是割點(diǎn)，當(dāng)且僅當(dāng)滿足下面的條件1或2：

1. 如果節(jié)點(diǎn)是總的DFS樹的根，該節(jié)點(diǎn)有多于1個(gè)的子樹。
2. 如果節(jié)點(diǎn)不是總的DFS樹的根，該節(jié)點(diǎn)存在一顆子樹，子樹的根節(jié)點(diǎn)為，且。

一條邊是橋，當(dāng)且僅當(dāng)邊沒有重邊，且。

需要使用到的全局變量的定義：

int N; // N表示節(jié)點(diǎn)總個(gè)數(shù)
vector <int> E, cutp; // cutp存儲割點(diǎn)
int dfn[MAXN], low[MAXN], timer;
struct Edge{int from, to;};
vector <Edge> br; // br存儲橋

DFS搜索可以如下實(shí)現(xiàn)（參考代碼）：

// 這段代碼求橋時(shí)未考慮重邊的情況
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算法只需要調(diào)用上面的dfs函數(shù)即可，代碼如下：

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

附上一道練習(xí)題，鏈接洛谷P3388 【模板】割點(diǎn)（割頂）。

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;
}