Kosaraju求强联通分量.doc

有向图的强连通分量(Kosaraju算法)在有向图G上求强连通分量1、对G做dfs，记录每个节点结束访问的时间2、对G的所有边反向3、按（1）中记录的时间从大到小对新的图dfs4、得到的森林中每棵树对应一个强连通分量以下图为例。深搜时，我们给每个点加一个开始搜索时间戳（用表示）和一个结束搜索时间戳(用表示)。 这样从4开始搜索得到以下搜索序列：4,5,7,6,8,8,6,7,5,4 1,2,3,3,2,1仔细观察这个搜索序列我们发现：1）该图得到一个搜索树林共两个搜索树，一个以4为根（4能到达的所有点），一个以1为根（1能到达的所有点）。2）4能达到的所有点在搜索序列里面都挨在一起，4不能达到的点形成的搜索序列肯定在其右边。3）搜索序列的左右括号是成对出现的，满足括号匹配的原则。某个节点两端括住的节点都是他能到达的所有结点。最先开始访问的节点（左括号），肯定也是其搜在子树里面最后一个访问的节点（右括号）。第二步对图进行反向，再从4点进行深搜，相当于在反向前的原图中求出所有能到达4的点。第三步，按结束时间从大到小进行搜索。我们看搜索序列，最后一个点肯定是第一遍深搜时得到的最后一棵树的根r。从他开始深搜，相当于求出所有能达到树根r的点。这样得到的搜索子树肯定是一个强联通分量。问题1：以上图为例，第一遍搜索得到以4为根的子序列（设为S1）和以1为根的子树序列（设为s2），图反向后，再从1开始搜索，能搜到的元素肯定不会包含s1的元素，为什么？答：因为s1中的点都不能到达1，而第二遍搜索就是看哪些点能到达1，所以搜不到s1中的点。问题2：图反向后对4进行深搜，尽管1能到达4，为什么搜不到1？因为第一遍深搜时，4不能达到1，所以1肯定位于4的右边，而第二遍深搜是按照结束时间进行搜索的，在搜索4之前，已经搜完1，对1设置了删除标志，所以不会把1并入4的强联通分量。下面的程序只计算了强连通分量的个数，要求出每个强连通分量具体是什么稍稍改一点就可以了:)const maxn=1000;var i,m,n,x,y,ans,postid:longint; map:array1.maxn,1.maxnof boolean; chk:array1.maxnof boolean; post:array1.maxnof longint;procedure dfs_mark(id:longint);/第一遍深搜，求id能到达的所有点var i:longint;begin chkid:=true; for i:=1 to n do if (not chki)and mapid,i then dfs_mark(i); inc(postid); postpostid:=id;/id的结束时间是postidend;/procedure dfs_calc(id:longint);第二遍深搜，求所有能到达id的点var i:longint;begin chkid:=false; for i:=1 to n do if chki and mapi,id then dfs_calc(i);end;/begin readln(n); readln(m); for i:=1 to m do begin readln(x,y); mapx,y:=true; end; for i:=1 to n do if not chki then dfs_mark(i); for i:=n downto 1