什么是强连通分量
有向图强连通分量：在有向图G中，如果两个顶点vi,vj间（vi>vj）有一条从vi到vj的有向路径，同时还有一条从vj到vi的有向路径，则称两个顶点强连通。如果有向图G的每两个顶点都强连通，称G是一个强连通图。有向图的极大强连通子图，称为强连通分量。
强连通分量的个数
Kosaraju算法
Kosaraju算法可以求出有向图中的强连通分量个数，并且对分属于不同强连通分量的点进行标记。
算法描述：
(1) 第一次对图G进行DFS遍历，并在遍历过程中，记录每一个点的退出顺序。以下图为例：
如果以1为起点遍历，访问结点的顺序如下：
结点第二次被访问即为退出之时，那么我们可以得到结点的退出顺序：
(2)倒转每一条边的方向，构造出一个反图G’。然后按照退出顺序的逆序对反图进行第二次DFS遍历。我们按1、4、2、3、5的逆序第二次DFS遍历：
访问过程如下：
每次遍历得到的那些点即属于同一个强连通分量。1、4属于同一个强连通分量，2、3、5属于另一个强连通分量。
伪代码：
#include<iostream>
const int maxn=1000;
bool g[maxn][maxn];
int n,scc,dfn,topo[maxn];
bool flag[maxn]
void dfs(int v)
{
if(flag[v]) return;
flag[v]=1;
for(int i=0;i<n;i++)
if(g[v][i]&&!flag[i])
dfs(i);
topo[dfn++]=v;
}
void ndfs(int v)
{
if(flag[v]) return;
flag[v]=scc;
for(int i=0;i<n;i++ )
if(g[i][v]&&!flag[i])
ndfs(i);
}
void kosaraju()
{
for(int i=0;i<n;i++)
flag[i]=false;
for(int i=0;i<n;i++)
if(!flag[i])
dfs(i);
for(int i=0;i<n;i++)
flag[i]=false;
for(int i=dfn-1;i>=0;i--)
if(!flag[topo[i]])
{
scc++;
ndfs(topo[i]);
}
}