定义：
- 割点：在一个无向连通图中，若删除某点后，图变成不连通，则称该点为该图的割点。
- 桥：在一个无向连通图中，若删除某边后，图变成不连通，则称该边为该图的桥。
Tarjan算法求割点和桥的思路同样也基于对图的DFS：
-
表示
节点在DFS搜索中是第几个被搜索到的（时间戳）。
-
表示从在DFS搜索树中以
的最小值。
一个节点是割点，当且仅当满足下面的条件1或2：
- 如果节点
- 如果节点
，且
。
一条边是桥，当且仅当边
没有重边，且
。
需要使用到的全局变量的定义：
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;
}
