一、Tarjan求割点
对于无向图G，如果删除某个点x后，联通分量数目增加，则称点x是图G的割点。
如何求割点呢？一种简单的方法是采取枚举每个点，删除后用DFS求连通分量，这样时间复杂度是O(nm)，显然不很优。
我们把在结点a为根的子树(不包括a)的点集即为 S(a)，把不在a为根的子树中的点集即为 T(a)。
如图，如果将点2删除，那么点4可通过S(2)中的返祖边和T(2)连通，删除2对它没有影响；但S(2)中的点5，由于点5没有返祖边，因此和T(2)不连通，即点2是割点。
总结一下，得到如下结论：
对于某点x，若S(x)中存在至少一点y，满足y与T(x)之间没有任何边，则x是割点。
具体实现上，我们可以利用Tarjan算法记录dfn[x]和low[x]。于是问题转化成，结点x是否存在一个儿子y，使得low[y]≥dfn[x]。我们只需一次DFS即可，总时间复杂度O(n+m)。
注意：对根必须单判，根要有至少两个子树才能算作割点。
参考程序如下：
1 #include
2 #define int long long
3 using namespacestd;4 const int N=1e5+5;5 int n,m,x,y,cnt=1,hd[N],to[N<<1],nxt[N<<1],dfn[N],low[N],num,root;6 boolg[N];7 void add(int x,inty){8 to[++cnt]=y,nxt[cnt]=hd[x],hd[x]=cnt;9 }10 void tarjan(intx){11 dfn[x]=low[x]=++num;12 int flag=0;13 for(int i=hd[x];i;i=nxt[i]){14 int y=to[i];15 if(!dfn[y]){16 tarjan(y),low[x]=min(low[x],low[y]);17 if(low[y]>=dfn[x]){18 flag++;19 if(x!=root||flag>1) g[x]=1;20 }21 }22 else low[x]=min(low[x],dfn[y]);23 }24 }25 signed main(){26 //freopen(".in","r",stdin);27 //freopen(".out","w",stdout);
28 scanf("%lld%lld",&n,&m);29 for(int i=1;i<=m;i++){30 scanf("%lld%lld",&x,&y);31 if(x==y) continue;32 add(x,y),add(y,x);33 }34 for(int i=1;i<=n;i++)35 if(!dfn[i]) root=i,tarjan(i);36 for(int i=1;i<=n;i++)37 if(g[i]) printf("%lld",i); //输出的是割点
38 return 0;39 }
二、Tarjan求割边
桥(割边)：无向连通图中，去掉一条边，图中的连通分量数增加，则这条边，称为桥或者割边。
判断桥：一条无向边(x,y)是桥，当且仅当(x,y)为树枝边，且满足 dfn(x)
因为遍历的是无向图，所以从每个点x出发，总能访问到它的父节点fa。根据low的计算方法，(x,fa)属于搜索树上的边，且fa不是x的子节点，故不能用fa的时间戳来更新low[x]。
如果仅记录每个节点的父节点，会无法处理重边的情况。当x与fa之间有多条边时，(x,fa)一定不是桥。在这些重复的边中，只有一条算是“搜索树上的边”，其他的几条都不算。故有重边时，dfn[fa]能用来更新low[x]。
改为记录“递归进入每个节点的边的编号”。编号可认为是边在邻接表中存储的下标位置。把无向图的每一条边看做双向边，成对存储在下标里。若沿着编号为i的边递归进入了节点x，则忽略从x出发的编号i xor 1的边，通过其他边计算low[x]即可。
1 #include
2 #define int long long
3 using namespacestd;4 const int N=1e5+5;5 int n,m,x,y,cnt=1,hd[N],to[N<<1],nxt[N<<1],dfn[N],low[N],num;6 bool g[N<<1];7 void add(int x,inty){8 to[++cnt]=y,nxt[cnt]=hd[x],hd[x]=cnt;9 }10 void tarjan(int x,intfa){11 dfn[x]=low[x]=++num;12 for(int i=hd[x];i;i=nxt[i]){13 int y=to[i];14 if(!dfn[y]){15 tarjan(y,i);16 low[x]=min(low[x],low[y]);17 if(low[y]>dfn[x]) g[i]=g[i^1]=1;18 }19 else if(i!=(fa^1)) low[x]=min(low[x],dfn[y]);20 }21 }22 signed main(){23 //freopen(".in","r",stdin);24 //freopen(".out","w",stdout);
25 scanf("%lld%lld",&n,&m);26 for(int i=1;i<=m;i++){27 scanf("%lld%lld",&x,&y);28 add(x,y),add(y,x);29 }30 for(int i=1;i<=n;i++)31 if(!dfn[i]) tarjan(i,0);32 for(int i=2;i
三、例题
Luogu P1656 炸铁路
题目链接思路：直接求割边，然后排序即可。
1 #include
2 #define int long long
3 using namespacestd;4 const int N=1e5+5;5 int n,m,x,y,cnt=1,hd[N],to[N<<1],nxt[N<<1],dfn[N],low[N],num,sum;6 bool g[N<<1];7 structdata{8 intx,y;9 }a[N];10 boolcmp(data x,data y){11 if(x.x!=y.x) return x.xdfn[x]) g[i]=g[i^1]=1;25 }26 else if(i!=(fa^1)) low[x]=min(low[x],dfn[y]);27 }28 }29 signed main(){30 //freopen(".in","r",stdin);31 //freopen(".out","w",stdout);
32 scanf("%lld%lld",&n,&m);33 for(int i=1;i<=m;i++){34 scanf("%lld%lld",&x,&y);35 add(x,y),add(y,x);36 }37 for(int i=1;i<=n;i++)38 if(!dfn[i]) tarjan(i,0);39 for(int i=2;ia[i].y) swap(a[i].x,a[i].y);44 printf("%lld %lld\n",a[i].x,a[i].y);45 }46 return 0;47 }
Luogu P3388 「模板」割点(割顶)
题目链接思路：板子题。直接上代码：
1 #include
2 #define int long long
3 using namespacestd;4 const int N=1e5+5;5 int n,m,x,y,cnt=1,hd[N],to[N<<1],nxt[N<<1],dfn[N],low[N],num,root,sum;6 boolg[N];7 void add(int x,inty){8 to[++cnt]=y,nxt[cnt]=hd[x],hd[x]=cnt;9 }10 void tarjan(intx){11 dfn[x]=low[x]=++num;12 int flag=0;13 for(int i=hd[x];i;i=nxt[i]){14 int y=to[i];15 if(!dfn[y]){16 tarjan(y),low[x]=min(low[x],low[y]);17 if(low[y]>=dfn[x]){18 flag++;19 if(x!=root||flag>1) g[x]=1;20 }21 }22 else low[x]=min(low[x],dfn[y]);23 }24 }25 signed main(){26 //freopen(".in","r",stdin);27 //freopen(".out","w",stdout);
28 scanf("%lld%lld",&n,&m);29 for(int i=1;i<=m;i++){30 scanf("%lld%lld",&x,&y);31 if(x==y) continue;32 add(x,y),add(y,x);33 }34 for(int i=1;i<=n;i++)35 if(!dfn[i]) root=i,tarjan(i);36 for(int i=1;i<=n;i++)37 if(g[i]) sum++;38 printf("%lld\n",sum);39 for(int i=1;i<=n;i++)40 if(g[i]) printf("%lld",i);41 return 0;42 }
咕咕咕……先占个坑
我只会打板子啊
Dls教教我
