在有向图G中，如果两个顶点间至少存在一条路径，称两个顶点强连通(strongly connected)。如果有向图G的每两个顶点都强连通，称G是一个强连通图。非强连通图有向图的极大强连通子图，称为强连通分量(strongly connected components)。
这里使用的是tarjan的算法，具体可以参考： http://www.cppblog.com/sosi/archive/2010/09/26/127797.aspx
下面是我的代码：
#include
using namespace std;
int sta[10005],belong[10005],sum[10005]={0},fin[10005]={0};
bool insta[10005]={0};
int e[50005][2],ee[50005][2];
int mik[10005]={0},low[10005],tong[10005],ton[10005]={0},kai[10005]={0};
int index,top,zu,i,j,m,n,k,s,t,shu,jieguo;
void tarjan(int i){
int now,jj;
mik[i]=low[i]=++index;
insta[i]=true;
sta[++top]=i;
for (jj=ton[i];jjn>>m;
for(i=0;i>ee[i][0]>>ee[i][1];
tong[(ee[i][0])]++;
}
for(i=1;i tong[i]+=tong[i-1];
ton[i+1]=tong[i];
kai[i+1]=tong[i];
}
for(i=0;i<m;i++){
k=kai[(ee[i][0])]++;
e[k][0]=ee[i][0];
e[k][1]=ee[i][1];
tong[(ee[i][0])]++;
}
top=0;
zu=0;
index=0;
for (i=1;i<n+1;i++)
if (!mik[i]) tarjan(i);
for (i=0;i<m;i++){
if (belong[(e[i][0])]!=belong[(e[i][1])]){
fin[(belong[(e[i][0])])]++;
}
}
for (i=1;i shu++;
jieguo=i;
}
if (shu==1) cout<<sum[jieguo]<<endl;
else cout<<0<<endl;
return 0;
}
