tarjan

tarjan寻找出度为0的强连通分量，从小到大输出此强连通分量中的点

poj 2553 The Bottom of a Graph
图存在多个强连通分量，强连通分量内的所有点的行为可以压缩为一个点的行为：若强连通分量的一个点可以到达其他强连通分量，则该强连通分量内的所有点均可以到达其他强连通分量；若强连通分量可以被其他强连通分量的点到达，则该强连通分量内的所有点均可以被其他强连通分量的点到达。因此，将图的强连通分量缩成一个点是一个经常会进行的操作。

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<cstring>
#include<stack>
#define M 5500
using namespace std;
int dfn[M],low[M];
int tot,sig,n,m;
int vis[M];
int col[M];
int dep[M];
stack<int>s;
vector<int>vep[M];
void init( )
{
      tot=sig=0;
      memset(dep,0,sizeof(dep));
      memset(vis,0,sizeof(vis));
      memset(dfn,0,sizeof(dfn));
      memset(low,0,sizeof(low));
      for(int i=0;i<M;i++)
      {
            vep[i].clear( );
      }
}
void tarjan(int x)
{
      dfn[x]=low[x]=++tot;
      s.push(x);
      vis[x]=1;
      for(int i=0;i<vep[x].size( );i++)
      {
            int j=vep[x][i];
            if(!dfn[j])
            {
                  tarjan(j);
                  low[x]=min(low[x],low[j]);
            }
            else if(vis[j])
            {
                  low[x]=min(low[x],dfn[j]);
            }
      }
      if(dfn[x]==low[x])
      {
            sig++;//连通分量个数
            int k;
            do
            {
                  k=s.top( );
                  vis[k]=0;
                  col[k]=sig;//每个点属于那个连通分量
                  s.pop( );
            }while(x!=k);
      }
      return ;
}
void solve(int n)
{
      for(int i=1;i<=n;i++)
      {
            if(!dfn[i])
            {
                  tarjan(i);
            }
      }
      //cout<<sig<<endl;
      for(int i=1;i<=n;i++)
      {
            for(int j=0;j<vep[i].size( );j++)
            {
                  int v=vep[i][j];
                  if(col[i]!=col[v])
                  {
                        dep[col[i]]++;//每个点对应的连通分量的出度
                  }
            }
      }
      for(int i=1;i<=n;i++)
      {
            if(dep[col[i]]==0)
            {
                  cout<<i<<" ";
            }
      }
      cout<<endl;
      return ;
}
int main( )
{
      int x,y;
      while(cin>>n>>m&&n)
      {
            init( );
            for(int i=1;i<=m;i++)
            {
                  cin>>x>>y;
                  vep[x].push_back(y);
            }
            solve(n);

      }
      return 0;
}