给定无向图G=（V，E）：
若对于x∈V，从图中删去节点x以及所有与节点x相关联的边后，G分裂成两个或两个以上不相连的子图，则称x为G的割点。
若对于e∈E，从图中删去边e后，G分裂成两个不相连的子图，则称e为G的桥或者割边。
根据著名的计算机学家Robert Tarjan（对，就是那个LCA算法的Tarjan）的名字命名的Tarjan算法能够在线性的时间内求出无向图的割点与桥。
Tarjan算法基于无向图的深度优先遍历。
在图的深度优先遍历的过程中，按照每一个节点第一次被访问的时间顺序，给予N个节点1~N的整数标记，该标记就被称为“时间戳”记为dfn[x]。
在无向图中任选一个节点出发进行深度优先遍历，每个点只访问一次。所有发生递归的边（x，y）构成一棵树（就是深度优先遍历中用vis[x]数组标记，防止重复走的边以外的边），我们把它称为“无向连通图的搜索树”，当然一般无向图（不一定连通）的各个连通块的搜索树构成无向图的“搜索森林”。
除了时间戳之外，Tarjan算法还引入了一个“追溯值”low[x]。设subtree（x）表示搜索树中以x为根的子树。low[x]定义为以下两种节点的时间戳最小值：
为了计算low[x]，我们先初始化为low[x]=dfn[x]（按道理根节点的时间戳比以它为根的子树中的节点的时间戳都小），然后考虑从x出发的所有边（x，y）：
无向边（x，y）是割边，当且仅当搜索树上存在x的一个子节点y，满足：
dfn[x]<low[y]
根据定义，dfn[x]<low[y]说明从subtree（y）出发，在不经过边（x，y）的前提下，不管走那条边都无法到达x或者比x更早访问的节点（若能到达，则追溯值应该>=dfn[x]），换句话说，将边（x，y）删除之后，subtree（y）与x无边相连，与比x更早访问的节点无边相连，图就被裂成了两部分，所以（x，y）是割边。
若对于x的任意子节点，都有dfn[x]>=low[y]，则说明每一个subtree（y）都能绕行其他边到达x或比x更早访问的节点，那么（x，y）就自然不是割边。
还有，割边一定是搜索树中的边，并且一个简单环中的边一定都不是割边。
特别需要注意，因为我们遍历的是无向图，所以从每一个点x出发，总能访问到它的父节点fa。根据low的计算方法（x，fa）属于搜索树上的边，且fa不是x的子节点，故不能用fa的时间戳来更新low[x]。
但是如果仅记录每一个节点的父节点，会无法处理重边的情况——当x与fa之间有多条边时，（x，fa）的任意一条边均不是割边。在这些重复的边中，只有一条算是“搜索树上的边”，其他的几条均不算。故有重边时，dfn[fa]能用来更新low[x]。
一个好的解决方法是：改为记录“递归进入每个节点的边的编号”（这样就能防止通过搜索树上的边访问fa又能处理重边了）。我们用邻接表“成对变换”的储存技巧来实现这一点。
附上代码:
1 #include<bits/stdc++.h> 2 using namespace std; 3 const int SIZE=100010; 4 int head[SIZE],ver[2*SIZE],nxt[2*SIZE]; 5 int dfn[SIZE],low[SIZE],n,m,tot,num; 6 bool bridge[SIZE*2]; 7 void add(int x,int y){ 8 ver[++tot]=y,nxt[tot]=head[x],head[x]=tot; 9 } 10 11 void tarjan(int x,int in_edge){ 12 dfn[x]=low[x]=++num//追溯值初始化为时间戳 13 for(int i=head[x];i;i=nxt[i]){ 14 int y=ver[i]; 15 if(!dfn[y]){//在搜索树上 16 tarjan(y,i); 17 low[x]=min(low[x],low[y]); 18 if(low[y]>dfn[x]) 19 bridge[i]=bridge[i^1]=true; 20 } 21 else if(i!=in_edge^1){//不在搜索树上 22 low[x]=min(low[x],dfn[y]); 23 } 24 } 25 } 26 27 int main(){ 28 cin>>n>>m; 29 tot=1; 30 for(int i=1;i<=m;++i){ 31 int x,y; 32 scanf("%d%d",&x,&y); 33 add(x,y),add(y,x);//无向边成对储存 34 } 35 for(int i=1;i<=n;++i)//对于无向图的每一个连通块 36 if(!dfn[i]) tarjan(i,0); 37 for(int i=2;i<tot;i+=2){ 38 if(bridge[i]) 39 printf("%d%d\n",ver[i^1],ver[i]); 40 } 41 return 0; 42 }
若x不是搜索树的根节点（深度优先遍历的起点），则x是割点当且仅当搜索树上存在x的一个子节点y，满足：
dfn[x]<=low[y]
特别地，如果x是搜索树的根节点，那么x是割边当且仅当存在两个子节点满足那样的条件。
证明方法与割边类似。
因为割点的判定法则是小于等于号，所以在求割点时，不必考虑父节点和重边的问题，从x出发的所有点的时间戳都可以用来更新low[x]。
附上代码：
1 #include<bits/stdc++.h> 2 using namespace std; 3 const int N=20001,M=100001; 4 int head[N],ver[2*M],nxt[2*M]; 5 int dfn[N],low[N]; 6 int n,m,tot,num,root; 7 bool cut[N]; 8 9 void add(int x,int y){ 10 ver[++tot]=y,nxt[tot]=head[x],head[x]=tot; 11 } 12 13 void tarjan(int x){ 14 dfn[x]=low[x]=++num; 15 int flag=0; 16 for(int i=head[x];i;i=nxt[i]){ 17 int y=ver[i]; 18 if(!dfn[y]){ 19 tarjan(y); 20 low[x]=min(low[x],low[y]); 21 if(low[y]>=dfn[x]){ 22 flag++;//防止是根节点的情况 23 if(x!=root || flag>1) 24 cut[x]=true; 25 } 26 }else low[x]=min(low[x],dfn[y]); 27 } 28 } 29 30 int main(){ 31 scanf("%d%d",&n,&m); 32 tot=1; 33 for(int i=1;i<=m;++i){ 34 int x,y; 35 scanf("%d%d",&x,&y); 36 if(x==y) continue; 37 add(x,y),add(y,x); 38 } 39 for(int i=1;i<=n;++i) 40 if(!dfn[i]) root=i,tarjan(i); 41 for(int i=1;i<=n;++i){ 42 if(cut[i]) cout<<i<<" "; 43 } 44 return 0; 45 }
原文：https://www.cnblogs.com/Asika3912333/p/11372797.html