强连通分量算法有3个之多，现在介绍这种名字叫做kosaraju算法。
这个算法基于两个事实，1.原图G与逆置图GT拥有相同的强连通分量，这肯定是正确的
2.任意一个子节点存放皆后于父节点，也就是说所有只有当所有子节点都入栈了，父节点才入栈
这种在递归调用之后将顶点入队列的方式叫逆后续排序(reverse post)，在无环图中这种排序方式就是拓扑排序。
简要证明：
1. 第一次DFS有向图G时，最后记录下的节点必为最后一棵生成树的根节点。
证明：假设最后记录下节点不是树根，则必存在一节点为树根，且树根节点必为此节点祖先；而由后根序访问可知祖先节点比此节点更晚访问，矛盾；原命题成立
2. 第一次DFS的生成森林中，取两节点A、B，满足：B比A更晚记录下,且B不是A的祖先(即在第一次DFS中，A、B处于不同的生成树中)；则在第二次DFS的生成森林中，B不是A的祖先，且A也不是B的祖先(即在第二次DFS中，A、B处于不同的生成树中)。
证明：假设在第二次DFS的生成森林中，B是A的祖先，则反图GT中存在B到A路径，即第一次DFS生成森林中，A是B的祖先，则A必比B更晚记录下，矛盾；假设在第二次DFS的生成森林中，A是B的祖先，则反图GT中存在A到B路径，即第一次DFS生成森林中，B是A的祖先,矛盾；原命题成立
3. 按上述步骤求出的必为强连通分量
证明：首先，证明2保证了第二次DFS中的每一棵树都是第一次DFS中的某棵树或某棵树的子树。其次，对于第二次DFS中的每棵树，第一次DFS保证了从根到其子孙的连通性，第二次DFS保证了根到子孙的反向连通性(即子孙到根的连通性)；由此，此树中的每个节点都通过其根相互连通。
从以上的理解可以看出，Kosaraju算法是有局限的，比如图中强连通分量是嵌套的，Kosaraju就会出现麻烦了。
代码挺短的，但是调了一晚上
#include<cstdio> #include<cstring> #define N 10000+10 #define M 500000+10 using namespace std; int head1[N],num1,head2[N],num2; struct edge{ int next,to; }e1[M],e2[M]; int stack[N],vis[N],scc[N],scc_cnt; void add1(int from,int to) { e1[++num1].next=head1[from]; e1[num1].to=to; head1[from]=num1; } void add2(int from,int to) { e2[++num2].next=head2[from]; e2[num2].to=to; head2[from]=num2; } int tot; void Kosaraju1(int u) { vis[u]=1; for(int i=head1[u];i;i=e1[i].next) { int v=e1[i].to; if(!vis[v])Kosaraju1(v); } stack[++tot]=u; } void Kosaraju2(int u) { scc[u]=scc_cnt; //vis[u]=0; for(int i=head2[u];i;i=e2[i].next) { int v=e2[i].to; if(!scc[v]) Kosaraju2(v); } } int main() { int n,m; scanf("%d%d",&n,&m); int x,y; for(int i=1;i<=m;i++){scanf("%d%d",&x,&y);add1(x,y);add2(y,x);} for(int i=1;i<=n;i++) if(!vis[i])Kosaraju1(i); for(int i=n;i>=1;i--){ if(!scc[stack[i]]){scc_cnt++;Kosaraju2(stack[i]);} } printf("%d",scc_cnt); return 0;