资源描述：
《有向图的强连通分量》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、强连通分量一个有向图中，如果节点i能够通过一些边到达节点j，就简写成i能到达j。如果对于任意两个节点i,j均有i能到达j或j能到达i，则说此图是连通的。如果对于任意两个节点i,j均有i能到达j且j能到达i，则说此图是强连通的。对于一个无向图，说强联通没有意义，因为此时强连通就是连通。而对于一个有向图，它不一定是强连通的，但可以分为几个极大的强连通子图（“极大”的意思是再加入任何一个顶点就不满足强连通了）。这些子图叫做这个有向图的强连通分量。在上图中，强连通分量是A{1},B{2,4},C{3,5,6,7}。在一个强连通分量中的节点由于有着
2、相似的拓扑性质，所以我们可以将其紧缩为一个节点（这让我想到了什么？化学里的“族”），于是就大大减小了图的规模。比如上图紧缩为A,B,C三个节点后，整个图就成为了B←A→C的简单形式。所以强连通分量是一个很有意义的东西。然而如果根据定义，对每个节点进行一次O(n2)的DFS以求出它所能到达的顶点的话，整个算法的时间复杂度就是迟钝的O(n3)。下面将介绍两种用O(n2)求强连通分量的算法：Kosaraju算法和Tarjan算法。Kosaraju算法Kosaraju算法基于以下思想：强连通分量一定是某种DFS形成的DFS树森林。Kosaraju
3、算法给出了更具体的方式：①任意进行一次DFS，记录下每个节点的结束时间戳f[i]。②按f[i]的大小对节点进行排序（从小到大）。③以②的排序结果为顺序再进行一次DFS，所得的DFS树森林即为强连通分量。这次DFS可以用Floodfill进行，把每个强连通分量标上不同序号。（这就是OI界传说中的“求强连两遍DFS的算法”）比如上图，我们可以得到：d[1]=1f[1]=14d[2]=2f[2]=5d[3]=6f[3]=13d[4]=3f[4]=4d[5]=7f[5]=8d[6]=9f[6]=12d[7]=10f[7]=11根据f[i]排序得：
4、④②⑤⑦⑥③①（发现了什么？就是后序遍历），再按照这个顺序进行DFS即可。程序：vara:array[1..1000,1..1000]oflongint;b,flag:array[1..1000]oflongint;n,i,j,m,k:longint;proceduredfs(x:longint);varj:longint;beginflag[x]:=1;forj:=1tondoif(flag[j]=0)and(a[x,j]>0)thendfs(j);inc(m);b[m]:=x;end;procedurefill(x,k:longint
5、);varj:longint;beginflag[x]:=k;forj:=ndownto1doif(flag[b[j]]=0)and(a[b[j],x]>0)thenfill(b[j],k);end;beginreadln(n);fori:=1tondobeginforj:=1tondoread(a[i,j]);readln;end;m:=0;fillchar(flag,sizeof(flag),0);fori:=1tondoifflag[i]=0thendfs(i);fillchar(flag,sizeof(flag),0);k:=0;
6、fori:=ndownto1doifflag[b[i]]=0thenbegininc(k);fill(b[i],k);end;fori:=1tokdobeginforj:=1tondoifflag[j]=ithenwrite(j,'');writeln;end;end.Tarjan算法Tarjan算法只要一遍DFS，效率高于Kosaraju。它在技术上有了很大改进。它基于的思想是：强连通分量是DFS树中的子树（无论你如何进行DFS）。Tarjan算法的过程是：①在DFS树中，设low[x]是x或x的后代能够达到的最高的祖先。初始化时low
7、[x]设为x。②进行DFS，在结束节点x时计算low[x]。计算的方法是：找出x能够到达的所有节点i，应保证low[i]是x的祖先，即low[i]是灰点。low[x]=highest(low[i])，即d[low[i]]最小。③若low[x]=x，则以x为根的子树就是一个强连通分量，输出并将其从树中删去。比如上图（又是上图。。没办法，图片空间有限制），我们依次得出：low[4]=low[2]=2low[2]=low[4]=2//{4,2}为强连通分量low[5]=low[3]=3low[7]=low[5]=3low[6]=low[7]=3
8、low[3]=low[6]=3//{5,7,6,3}为强连通分量low[1]=1//{1}为强连通分量感谢ChenGang同学的提醒，我原来的程序中的输出有些问题。现在采用堆栈的方法，dfs到
