照着别人的博客写了生平第一题tarjan强连通分量，不得不佩服tarjan，我笔算了tarjan，整个过程是有了一定的理解，但是为什么是正确的，只能膜拜tarjan了。
下面的博客写的很好，对tarjan强连通分量做了比较详细的解释
http://blog.sina.com.cn/s/blog_62ebd4410100g53w.html
下面的博客有算法的流程（作为不时之需）
http://www.byvoid.com/blog/scc-tarjan/
#include<iostream> using namespace std; #define N 10005 typedef struct node* pointer; struct node { int ver; pointer next; }; int low[N],ord[N],cnt,scnt,stk[N],id[N]; bool map[N],instk[N]; pointer g[N]; void insert(int u,int v) { pointer ptr=new node; ptr->ver=v; ptr->next=g[u]; g[u]=ptr; } void tarjan(int e) { int t; pointer ptr; low[e]=++cnt; ord[e]=cnt; stk[++stk[0]]=e; instk[e]=true; ptr=g[e]; while(ptr!=NULL) { t=ptr->ver; if(!ord[t]) { tarjan(t); if(low[e]>low[t]) low[e]=low[t]; } else if(instk[t]&&low[e]>ord[t]) low[e]=ord[t]; ptr=ptr->next; } if(low[e]==ord[e]) { scnt++; do { t=stk[stk[0]--]; id[t]=scnt; instk[t]=false; }while(t!=e); } return; } void find_component(int n) { int i; memset(ord,0,sizeof(ord)); memset(instk,false,sizeof(instk)); cnt=0,scnt=0,stk[0]=0; for(i=1;i<=n;i++) if(!ord[i]) tarjan(i); return ; } int main() { int n,m,x,y,i,e,ans,flag; scanf("%d%d",&n,&m); for(i=1;i<=n;i++) g[i]=NULL; for(i=1;i<=m;i++) { scanf("%d%d",&x,&y); insert(x,y); } find_component(n); memset(map,0,sizeof(map)); ans=0; for(i=1;i<=n;i++) { if(id[i]==1) ans++; pointer ptr=g[i]; while(ptr!=NULL) { e=ptr->ver; if(id[i]!=id[e]&&!map[id[i]]) map[id[i]]=1; ptr=ptr->next; } } flag=0; for(i=1;i<=scnt;i++) if(!map[i]) flag++; if(flag>1) printf("0/n"); else printf("%d/n",ans); return 0; }
