tarjan

tarjan:寻找出度为0的强连通分量，并求出该强连通分量中有多少个点。

#include<bits/stdc++.h>
#define ll long long
#define M 1000100
using namespace std;
int low[M],dnf[M],tot,temp,sig;
int vis[M],n,m;
int col[M],du[M];
int dep[M];
stack<int> s;
vector<int>vep[M];
void init( )
{
      memset(low,0,sizeof(low));
      memset(dep,0,sizeof(dep));
      memset(col,0,sizeof(col));
      memset(du,0,sizeof(du));
      memset(dnf,0,sizeof(dnf));
      memset(vis,0,sizeof(vis));
      tot=temp=sig=0;
      for(int i=0;i<M;i++)
      {
            vep[i].clear( );
      }
}
void tarjan(int x)
{
      low[x]=dnf[x]=++tot;
      vis[x]=1;
      s.push(x);
      for(int i=0;i<vep[x].size( );i++)
      {
            int j=vep[x][i];
            if(dnf[j]==0)
            {
                  tarjan(j);
                  low[x]=min(low[x],low[j]);
            }
            else if(vis[j])
            {
                  low[x]=min(low[x],dnf[j]);
            }
      }
      if(low[x]==dnf[x])
      {
            sig++;
            int k;
            do
            {
                  k=s.top( );
                  col[k]=sig;
                  du[sig]++;
                  vis[k]=0;
                  s.pop( );
            }while(x!=k);
      }
      return ;
}
int main( )
{
      cin>>n>>m;
      init( );
      int x,y;
      for(int i=1;i<=m;i++)
      {
            cin>>x>>y;
            vep[x].push_back(y);
      }
      for(int i=1;i<=n;i++)
      {
            if(!dnf[i])
            {
                  tarjan(i);
            }
      }
      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]]++;
                  }
            }
      }
      int cnt=0,ans=0;
      for(int i=1;i<=sig;i++)
      {
            if(dep[i]==0)
            {
                  ans+=du[i];
                  cnt++;
            }
      }
      if(cnt==1)
      {
            cout<<ans<<endl;
      }
      else
      {
            cout<<0<<endl;
      }
      return 0;
}