Tarjan大法之强连通分量与割点和桥
Danny_boodman · · 个人记录
天天膜tarjan,图论我很强。(✪ω✪)
记得noip2017前把塔老爷子当电脑桌面，然后，嗯......
就没有然后了。
掉到二队电脑每次关机就会清空桌面。 于是就坚定了我学好tarjan的志向。 好了，废话少说，开始我们的图论之旅。
我们先看一下它到底有什么鬼用。
求这个图中的强联通分量
先了解一些概念
有向图强连通分量：在有向图G中，如果两个顶点vi,vj间（vi>vj）有一条从vi到vj的有向路径，同时还有一条从vj到vi的有向路径，则称两个顶点强连通(strongly connected)。
如果有向图G的每两个顶点都强连通，称G是一个强连通图。有向图的极大强连通子图，称为强连通分量(strongly connected components)。把每个强联通分量看成一个集合，把每个集合看成一个点，那么所有SCC就行成了一个DAG（有向无环图）,就是著名的缩点。
比如下图
1、2、3能相互到达，所以他们就是一个强联通分量。
那怎么求呢？就要用到强大的tarjan算法。
tarjan算法：混合了dfs，玄学打标记，堆栈，搜索树等的奇葩又天才的算法（嗯，应该不是我发明的）
那么我们来看上一个图，嗯，自然而然地想到DFS，然后就行成了下面的搜索树
是不是有点头皮发麻了呢？一大坨线连过去连过来，我们怎么把他们分开形成一个个SCC呢？那就用要用到两个玄学的标记。
DFN:时间戳，表示他是第几个被访问的。
LOW:表示这个节点能向上到达的最老祖先的时间戳。
初始化时DFN=LOW
我们在搜索时把节点一个个入栈，如果在我们回溯是发现DFN==LOW，那么表示他是该子树的根，那么把该子树压出栈即可。
那大致算法框架就出来了：每次发现一个新节点就入栈，无路可走时就向后转——回溯，回溯时用子节点更新父节点的LOW值以保证他的LOW值在以他为根的子树中最小。如果发现DFN==LOW，那么就按上面所说的搞一下就行了。
还不是很懂？那我们模拟一下。
出发
首先我们从一号小朋友出发，DNF[1]=LOW[1]=++timeclock=1，入栈
然后我们欢快地继续向后，发现了二号小朋友，DFN[2]=LOW[2]=++timeclock=2，入栈
继续跑.....发现后面有一只三号小朋友，DFN[3]=LOW[3]=++timeclock=3，入栈
继续走，发现后面竟然还有一个六号小朋友，DFN[6]=LOW[6]=++timeclock=4，入栈
继续......然而六号小朋友并没有拉上其他人了，于是回头一看，DFN[6]==LOW[6]，于是六号小朋友只有一个人孤独地吃果果了，出栈。
咔，找到一个SCC
继续往回走，LOW[3]=min(LOW[3],LOW[6])，然而并没有什么用，还是3。
然而我们发现DFN[3]==LOW[3]，三号小朋友也拉不上人了，于是他也能独享一份果果了。
咔，又找到一个SCC
又回到二了，LOW[2]=min(LOW[2],LOW[3])，也没什么用。
但我们发现二后面还拉了一个五号小朋友，于是我们去采访一下他
五号小朋友：“DFN[5]=LOW[5]=++timeclock=5”,入栈
本来我们应该去看一下六号小朋友，但他已经在吃果果了，不在栈中，我们就不要去打扰他了。
那去一号看看吧。
一号小朋友：“我是你爸爸的爸爸.......”，管他的，既然他在栈中，那就可能在我们要继续找的SCC中，那我们还是要更一波新，表示五号小朋友能够回到的最老祖先是一号小朋友，LOW[5]=DNF[1]=1。但就没有必要去访问了，溜了溜了。
溜到二号小朋友那里，LOW[2]=min(LOW[2],LOW[5])=1。
继续溜，溜到一号小朋友那里，LOW[1]=min(LOW[1],LOW[2])=1
有点意思了，但我们不急，因为一号节点还有子节点没有访问，所以，继续走。
发现了四号小朋友，DFN=LOW=++timeclock=6
继续走，发现了五号小盆友（怎么又是你，兄弟），发现他还在栈中，更新，开溜。LOW[4]=DFN[5]=5。
回家......回到一号节点。LOW[1]=min(LOW[1],LOW[4])=1
好了，没路可走了，DFN[1]==LOW[1],一二五四，排排坐，一起吃果果。
咔，没了
没了吗？不一定，万一你没有一次并没有采访完所有小盆友呢？所以我们应该在外面套一层循环以保证所有点被遍历。
OK，大致就这样，具体实现就看代码了吧
#include<iostream>
#include<stdio.h>
using namespace std;
int n,m,cnt,p,head[100010],low[100010],dfn[100010],timeclock;
int stack[100010],top,instack[100010],belong[100010];
struct ss{
int next,to;
};ss data[100010];
void add(int a,int b)
{
data[++p].to=b;
data[p].next=head[a];
head[a]=p;
}
void dfs(int a)
{
low[a]=dfn[a]=++timeclock;//初始化
instack[a]=1;
stack[++top]=a;//入栈
for(int i=head[a];i;i=data[i].next)
{
if(!dfn[data[i].to])
{
dfs(data[i].to);
low[a]=min(low[a],low[data[i].to]);//用子节点更新自己的LOW
}
else
if(instack[data[i].to])
low[a]=min(low[a],dfn[data[i].to]);//若是在栈中 ，比较父子关系，并更新。
}
if(dfn[a]==low[a])
{
cnt++;
while(stack[top+1]!=a)
{
belong[stack[top]]=cnt;
instack[stack[top--]]=0;
}
}
}
int main()
{
scanf("%d%d",&n,&m);
int a,b;
for(int i=1;i<=m;i++)
{
scanf("%d%d",&a,&b);
add(a,b);
}
for(int i=1;i<=n;i++)
{
if(!dfn[i])
{
dfs(i);
}
}
printf("%d ",cnt);
for(int i=1;i<=n;i++)
printf("%d ",belong[i]);
return 0;
}终于打完了，好累，但为了不用二队的刷新桌面的电脑，fighting!
附赠一个割点代码
外加定义：在一个无向图中，如果删掉点 x 后图的连通块数量增加，则称点 x 为图的割点。
外加图示
如果u点的子节点为v，v点他能返回的最老祖先比u点年轻或一样（即dfn[u]值<=low[v]），那么如果删去u点，那么v以下的点就会与v以上的点失去联系，就会产生新的连通块
也就是说如果在我们的搜索树上有一个点只有树边与祖先相连，而没有反向边连回祖先节点的话，那么它就是割点。就是没有这样的边
至于桥的道理也是差不多的
割点割点.....
#include<iostream>
#include<stdio.h>
using namespace std;
struct ss{
int next,to;
};ss data[200010];
int n,m,p,head[100010],ge[100010];
int timeclock,ans;
int low[100010],dfn[100010];
void add(int a,int b)
{
data[++p].to=b;
data[p].next=head[a];
head[a]=p;
}
void tarjan(int a,int fa)
{
int zj=0;
dfn[a]=low[a]=++timeclock;
for(int i=head[a];i;i=data[i].next)
{
int v=data[i].to;
if(!dfn[v])
{
tarjan(v,fa);
low[a]=min(low[a],low[v]);
if(low[v]>=dfn[a]&&a!=fa) ge[a]=1;
if(a==fa) zj++;
}
low[a]=min(low[a],dfn[v]);
}
if(a==fa&&zj>=2) ge[a]=1;
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++)
{
int u,v;
scanf("%d%d",&u,&v);
add(u,v);add(v,u);
}
for(int i=1;i<=n;i++)
if(!dfn[i])
tarjan(i,i);
for(int i=1;i<=n;i++)
if(ge[i]) ans++;
printf("%d\n",ans);
for(int i=1;i<=n;i++)
if(ge[i]) printf("%d ",i);
return 0;
}附赠一个桥的代码
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int N=2010;
int head[2010],num;
struct edge{
int last,v;
};
struct data{
int x,y;
};
data ss[400010];
edge e[400010];
void add(int from,int to)
{
e[++num].last=head[from];
e[num].v=to;
head[from]=num;
}
int flag[2010],dfn[2010],low[2010];
int bu[2010],bv[2010];
int tim=0,tot;
int cnt=0;
int cmp(const data & a,const data & b)
{
if(a.x<b.x)return 1;
if(a.x>b.x)return 0;
if(a.y<b.y)return 1;
return 0;
}
void dfs(int u,int fa)
{
tim++;
low[u]=dfn[u]=tim;
for(int i=head[u];i;i=e[i].last)
{
int v=e[i].v;
if(!dfn[v])
{
dfs(v,u);
low[u]=min(low[u],low[v]);
if(low[v]>dfn[u])
{
ss[++cnt].x=u;
ss[cnt].y=v;
}
}
else if(v!=fa)
{
low[u]=min(low[u],dfn[v]);
}
}
return;
}
int main()
{
int n,m;
scanf("%d%d",&n,&m);
int x,y;
for(int i=1;i<=m;i++)
{
scanf("%d%d",&x,&y);
add(x,y);
add(y,x);
}
cnt=0;
dfs(1,1);
sort(ss+1,ss+cnt+1,cmp);
printf("%d\n",cnt);
for(int i=1;i<=cnt;i++)
{
printf("%d %d\n",ss[i].x,ss[i].y);
}
return 0;
}