图论-求有向图的强连通分量（Kosaraju算法）

求有向图的强连通分量

Kosaraju算法可以求出有向图中的强连通分量个数，并且对分属于不同强连通分量的点进行标记。

(1) 第一次对图G进行DFS遍历，并在遍历过程中，记录每一个点的退出顺序。以下图为例：

G图

结点第二次被访问即为退出之时，那么我们可以得到结点的退出顺序

(2)倒转每一条边的方向，构造出一个反图G’。然后按照退出顺序的逆序对反图进行第二次DFS遍历。我们按1、4、2、3、5的逆序第二次DFS遍历：

G`图

访问过程如下：

每次遍历得到的那些点即属于同一个强连通分量。1、4属于同一个强连通分量，2、3、5属于另一个强连通分量。

测试数据：

输入：

5 7
1 4
1 5
1 2
2 3
3 5
4 1
5 2

输出：2

代码实现：

 1 #include<iostream>
 2 using namespace std;
 3 #define N 2010
 4 int map[N][N];
 5 int remap[N][N];
 6 int n,m;
 7 int vis[N];
 8 int post[N];
 9 int post_size;
10 int ans=0;
11 void dfs(int i)
12 {
13     vis[i]=1;
14     for(int j=1;j<=n;++j)
15     {
16         if(map[i][j]&&!vis[j])
17             dfs(j);
18     }
19     post[++post_size]=i;
20 }
21 void redfs(int i)
22 {
23     vis[i]=0;
24     for(int j=1;j<=n;++j)
25     {
26         if(vis[j]&&remap[i][j])
27             redfs(j);
28     }
29 }
30 int main()
31 {
32     cin>>n>>m;
33     for(int i=1;i<=m;++i)
34     {
35         int x,y;
36         cin>>x>>y;
37         map[x][y]=1;
38         remap[y][x]=1;
39     }
40     for(int i=1;i<=n;++i)
41     {
42         if(!vis[i])dfs(i);
43     }
44     for(int i=n;i>=1;--i)
45     {
46         if(vis[post[i]])
47         {
48             redfs(post[i]);
49             ans++;
50         }
51     }
52     cout<<ans;
53     return 0;
54 }