有向图的强连通分量.doc

强连通分量一个有向图中，如果节点i能够通过一些边到达节点j，就简写成i能到达j。如果对于任意两个节点i,j均有i能到达j或j能到达i，则说此图是连通的。如果对于任意两个节点i,j均有i能到达j且j能到达i，则说此图是强连通的。对于一个无向图，说强联通没有意义，因为此时强连通就是连通。而对于一个有向图，它不一定是强连通的，但可以分为几个极大的强连通子图（“极大”的意思是再加入任何一个顶点就不满足强连通了）。这些子图叫做这个有向图的强连通分量。在上图中，强连通分量是A1,B2,4,C3,5,6,7。在一个强连通分量中的节点由于有着相似的拓扑性质，所以我们可以将其紧缩为一个节点（这让我想到了什么？化学里的“族”），于是就大大减小了图的规模。比如上图紧缩为A,B,C三个节点后，整个图就成为了BAC的简单形式。所以强连通分量是一个很有意义的东西。然而如果根据定义，对每个节点进行一次O(n2)的DFS以求出它所能到达的顶点的话，整个算法的时间复杂度就是迟钝的O(n3)。下面将介绍两种用O(n2)求强连通分量的算法：Kosaraju算法和Tarjan算法。Kosaraju算法Kosaraju算法基于以下思想：强连通分量一定是某种DFS形成的DFS树森林。Kosaraju算法给出了更具体的方式：任意进行一次DFS，记录下每个节点的结束时间戳fi。按fi的大小对节点进行排序（从小到大）。以的排序结果为顺序再进行一次DFS，所得的DFS树森林即为强连通分量。这次DFS可以用Floodfill进行，把每个强连通分量标上不同序号。（这就是OI界传说中的“求强连两遍DFS的算法”）比如上图，我们可以得到：d1=1 f1=14d2=2 f2=5d3=6 f3=13d4=3 f4=4d5=7 f5=8d6=9 f6=12d7=10 f7=11根据fi排序得：（发现了什么？就是后序遍历），再按照这个顺序进行DFS即可。程序：var a:array1.1000,1.1000of longint; b,flag:array1.1000of longint; n,i,j,m,k:longint;procedure dfs(x:longint); var j:longint; begin flagx:=1; for j:=1 to n do if (flagj=0)and(ax,j0) then dfs(j); inc(m); bm:=x; end;procedure fill(x,k:longint); var j:longint; begin flagx:=k; for j:=n downto 1 do if (flagbj=0)and(abj,x0) then fill(bj,k); end;begin readln(n); for i:=1 to n do begin for j:=1 to n do read(ai,j); readln; end; m:=0; fillchar(flag,sizeof(flag),0); for i:=1 to n do if flagi=0 then dfs(i); fillchar(flag,sizeof(flag),0); k:=0; for i:=n downto 1 do if flagbi=0 then begin inc(k); fill(bi,k); end; for i:=1 to k do begin for j:=1 to n do if flagj=i then write(j, ); writeln; end;end.Tarjan算法Tarjan算法只要一遍DFS，效率高于Kosaraju。它在技术上有了很大改进。它基于的思想是：强连通分量是DFS树中的子树（无论你如何进行DFS）。Tarjan算法的过程是：在DFS树中，设lowx是x或x的后代能够达到的最高的祖先。初始化时lowx设为x。进行DFS，在结束节点x时计算lowx。计算的方法是：找出x能够到达的所有节点i，应保证lowi是x的祖先，即lowi是灰点。lowx=highest(lowi)，即dlowi最小。若lowx=x，则以x为根的子树就是一个强连通分量，输出并将其从树中删去。比如上图（又是上图。没办法，图片空间有限制），我们依次得出：low4=low2=2low2=low4=2 /4,2为强连通分量low5=low3=3low7=low5=3low6=low7=3low3=low6=3 /5,7,6,3为强连通分量low1=1 /1为强连通分量感谢ChenGang同学的提醒，我原来的程序中的输出有些问题。现在采用堆栈的方法，dfs到某一节点时将其入栈，当lowx=x时不断出栈，知道将x出栈为止，因为x是这个强连通分量的根。程序：var a,kl:array1.1000,1.1000of longint; d,f,low,stack:array1.1000of longint; i,j,n,time,h:longint;procedure dfs(x:longint); var i:longint; begin inc(time); dx:=time; inc(h); stackh:=x; for i:=1 to n do if ax,i0 then begin if di=0 then begin klx,i:=1; dfs(i); end; if (di0)and(fi=0) then klx,i:=2; if fi0 then begin if dxdi then klx,i:=3 else klx,i:=4; end; end; inc(time); fx:=time; for i:=1 to n do if ax,i0 then if (flowi=0)and(dlowi0) then lowx:=lowi; if lowx=x then begin while stackhx do begin write(stackh, ); dec(h); end; writeln(stackh); dec(h); end; end;begin readln(n); for i:=1 to n do begin for j:=1 to n do read(ai,j); readln; end; fillchar(d,sizeof(d),0); fillchar(d,sizeof(d),0); for i:=1 to n do lowi:=i; time:=0; fillchar(stack,sizeof(stack),0); h:=0; for i:=1 to n do if di=0 then dfs(i