1 #include
     
       2 #include
      
        3 #define M 50008 4 using namespace std; 5 int du[M],ti,ti1,cnt,head[M],head1[M],next1[10*M],u1[10*M],next[10*M],u[M],n,m,dfn[M],low[M],t,zhan[M],f[M],bel[M],sum[M]; 6 void jia(int a1,int a2) 7 { 8     cnt++; 9     next[cnt]=head[a1];10     head[a1]=cnt;11     u[cnt]=a2;12 }13 void jia1(int a1,int a2)14 {15     cnt++;16     next1[cnt]=head1[a1];17     head1[a1]=cnt;18     u1[cnt]=a2; 19     du[a1]++;20 }21 void tarjin(int a1)22 {23     dfn[a1]=low[a1]=++ti;24     f[a1]=1;25     t++;26     zhan[t]=a1;27     for(int i=head[a1];i;i=next[i])28       if(!dfn[u[i]])29         {30             tarjin(u[i]);31             low[a1]=min(low[a1],low[u[i]]);32         }33       else  if(f[u[i]])34                low[a1]=min(low[a1],dfn[u[i]]);35     if(dfn[a1]==low[a1])36       {37         ++ti1;38         int now=0;39         for(;now!=a1;)40           {41             now=zhan[t];42             bel[now]=ti1;43             sum[ti1]++;44             f[now]=0;45             t--;46           }47       }48 }49 void jian()50 {51     cnt=0;52     for(int i=1;i<=n;i++)53       for(int j=head[i];j;j=next[j])54         if(bel[i]!=bel[u[j]])55            jia1(bel[i],bel[u[j]]);56 }57 int main()58 {59     scanf("%d%d",&n,&m);60     for(int i=1;i<=m;i++)61       {62         int a1,a2;63         scanf("%d%d",&a1,&a2);64         jia(a1,a2);65       }66     for(int i=1;i<=n;i++)67       if(!dfn[i])68         tarjin(i);69     jian();70     int s=0,s1;71     for(int i=1;i<=ti1;i++)72       if(!du[i])73         {74             s++;75             s1=i;76         }77     if(s>1)78       printf("0");79     else80       printf("%d",sum[s1]);81     return 0;82 }
      
     

按题目建图后，用tarjan缩点，统计没有出度的联通块的个数，如果只有一个，输出这个联通块内点的个数，否则为零。