题目链接：http://poj.org/problem?id=3180

题目大意：求一个有向图的强连通分量

算法：求强连通分量首选tarjan算法

    这里简单说一下tarjan的思路

    时间戳是什么:在搜索时访问的最早时间

 

    维护dfn[u]表示u的时间戳

 

          low[u]表示u点所能回到的最早的祖先的时间戳

    开一个栈，把搜索的点入栈。搜索时遇到已经搜过的点，取low[u]和dfn[v]的最小值，回溯时取low[u]和low[v]的最小值(标记上传)传到dfn[u]<=low[u]时表示已经回溯到最上面的顶点了p，现在输出栈，直到输出p，此时输出的所有点属于一个强连通分量

1 #include 
     
       2 #include 
      
        3 #include 
       
         4 #include 
        
          5 #include 
         
           6 #include "algorithm" 7 using namespace std; 8 typedef long long LL; 9 const int MAX1=10005;10 const int MAX2=50005;11 int n,m;12 int tot,c;13 int dfn[MAX1],low[MAX1];14 int head[MAX1],adj[MAX2],next[MAX2];15 bool t[MAX1];16 int sta[MAX1];17 int ans;18 void addedge(int u,int v){19     tot++;20     adj[tot]=v;21     next[tot]=head[u];22     head[u]=tot;23 }24 void init(){25     int i,j;26     int u,v;27     scanf("%d%d",&n,&m);28     memset(next,0,sizeof(next));29     for (i=1;i<=m;i++)30     {scanf("%d%d",&u,&v);31      addedge(u,v);32     }33     memset(t,false,sizeof(t));34     ans=c=sta[0]=0;35 }36 int dfs(int x){37     int i,j;38     t[x]=true;39     sta[++sta[0]]=x;40     dfn[x]=++c;low[x]=dfn[x];41     for (i=head[x];i;i=next[i])42      if (t[adj[i]])43       low[x]=min(low[x],dfn[adj[i]]);44      else45      {j=dfs(adj[i]);46       low[x]=min(low[x],j);47      }48     j=0;49     if (low[x]>=dfn[x])50     {
   while (1)51      {j++;52       if (sta[sta[0]]==x)53       {sta[0]--;54        break;55       }56       sta[0]--;57      }58      if (j>1) ans++;59     }60     else return low[x];61 }62 int main(){63     freopen ("prom.in","r",stdin);64     freopen ("prom.out","w",stdout);65     init();int i,j;66     for (i=1;i<=n;i++)67      if (!t[i])68       j=dfs(i);69     printf("%d",ans);70     return 0;71 }72 73