Kosaraju算法

来自"NOCOW"

这个算法的较为普遍的版本是：

 1.对原图进行DFS并将出栈顺序进行逆序，得到的顺序就是拓扑顺序
 2.将原图每条边进行反向
 3.按照1中生成顺序再进行DFS染色染成同色的是一个强连通块
 合理性：如果是强连通子图，那么反向没有任何影响，依然是强连通子图。
        但如果是单向的边连通，反向后再按原序就无法访问了（因此反向处理是对非强连通块的过滤）

下面的算法并不一定是根据以上算法写的，在这里只是对求图的强连通分量算法做下介绍 --121.18.89.190 08:48 2008年10月17日 (CST)True1023

/*这是一个求图的强连通分量的算法。*/

#include <cstdio>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
#define NMAX 11000 
 
vector< vector< int > > path;
vector< vector< int > > npath;
int n,m, scc;
int order[NMAX], order_pos, id[NMAX], id_total[NMAX];
bool vis[NMAX];
int out_degre[NMAX];
 
void dfs(int pos)
{
	int i,j,l;
	vis[pos] = true;
	l = path[pos].size();
	for (i=0;i<l;i++) {
		j = path[pos][i];
		if (!vis[j]) {
			dfs(j);
		}
	}
	order[ order_pos ++ ] = pos;//make order
}
 
void ndfs(int pos)
{
	int i,j,l;
	vis[pos] = true;
	id[pos] = scc;
	l = npath[pos].size();
	for (i=0;i<l;i++) {
		j = npath[pos][i];
		if (!vis[j]) {
			ndfs(j);
		}
	}
}
 
void Kosaraju()
{
	int i,j,l;
	//dfs in original graph
	memset(vis, 0, sizeof(vis));
	for (i=1; i<=n ;i++) {
		if (!vis[i]) {
			dfs(i);
		}
	}
	//dfs in inverse graph
	memset(vis, 0, sizeof(vis));
	memset(id, 0, sizeof(id));
	scc = 1;
	for (i=order_pos-1; i>=0 ;i--) {
		if (!vis[ order[i] ]) {
			ndfs(order[i]);
			scc ++;
		}
	}
	//statist
	scc --;
	memset(id_total, 0, sizeof(id_total));
	for (i=1;i<=n;i++) {
		id_total[ id[i] ] ++;
	}
 
	memset(out_degre, 0, sizeof(out_degre));
	for (i=1;i<=n;i++) {
		l = path[i].size();
		int id1 = id[i];
		for (j=0;j<l;j++) {
			int id2 = id[ path[i][j] ];
			if (id1 != id2) {//id1 -> id2
				out_degre[id1] ++;
			}
		}
	}
	int ans_id,zero_degre = 0;
	for (i=1;i<=scc;i++) {
		if (out_degre[i] == 0) {
			zero_degre ++;
			ans_id = i;
		}
	}
 
	if (zero_degre > 1) {
		printf("0\n");
	}
	else {
		printf("%d\n",id_total[ ans_id ]);
	}
}
 
int main()
{
	int i,j;
	while (scanf("%d %d",&n,&m)==2) {
		path.resize(n+10);
		npath.resize(n+10);
		for (i=0;i<=n;i++) {
			path[i].clear();
			npath[i].clear();
		}
		order_pos = 0;
		//set graph
		for (i=0;i<m;i++) {
			int x,y;
			scanf("%d %d",&x,&y);
			path[x].push_back(y);
			npath[y].push_back(x);
		}
		Kosaraju();
	}
}

pascal版本
                         ——市守沐Samuel
{
  Kosaraju Algorithm
     By Samuel
    2009.11.04
}
program Kosaraju;
 
var
   link,link2:array[0..110,0..110]of longint;
   a:array[0..110]of longint;
   p:longint;
   rec:array[0..110]of boolean;
   col:array[0..110]of longint;
   color,n,i,j,x:longint;
 
function max(a,b:longint):longint;
begin
  if a>b then exit(a) else exit(b);
end;
procedure sou(x:longint);
var
   i:longint;
begin
  rec[x]:=true;
  for i:=1 to link[x,0] do
    if not rec[link[x,i]] then sou(link[x,i]);
  inc(p);
  a[p]:=x;
end;
 
procedure sou2(x:longint);
var
   i:longint;
begin
  col[x]:=color;
  for i:=1 to link2[x,0] do
    if col[link2[x,i]]=0 then sou2(link2[x,i]);
end;
 
BEGIN
  //assign(input,inf);reset(input);
  //assign(output,ouf);rewrite(output);
  readln(n);
  for i:=1 to n do
  begin
    read(x);
    while x<>0 do
    begin
      inc(link[i,0]);
      link[i,link[i,0]]:=x;
      inc(link2[x,0]);
      link2[x,link2[x,0]]:=i;  { 2.将原图每条边进行反向}
      read(x);
    end;
    readln;
  end;
  fillchar(rec,sizeof(rec),0);
  for i:=1 to n do             { 1.对原图进行DFS↓}
    if not rec[i] then sou(i);
  color:=0;
  for i:=p downto 1 do         {并将出栈顺序a[i]进行逆序，得到的顺序就是拓扑顺序}
    if col[a[i]]=0 then
    begin
      inc(color);
      sou2(a[i]);              {3.按照1中生成顺序再进行DFS染色染成同色的是一个强连通块}
    end;
  //close(input);close(output);
END.