【洛谷P2341】受欢迎的牛

受欢迎的牛

题目描述

一些可以当明星的牛，一定会构成一个强连通分量，我们可以先缩点，最后统计一下出度为零的强连通分量大小即可，

若出度为零的强连通分量个数大于1，则输出0

 #include<iostream>

 #include<cstring>

 #include<cstdio>

 using namespace std;

 #define N 10010

 #define M 100010

 int n,m,dfn[N],low[N],belong[N],du[N],cnt;

 int stack[N],top,size[N],k,head[N],num,tot;

 bool instack[N];

 struct NODE{

     int to,next;

 } e[M];

 inline int read(){

     int x=,f=; char c=getchar();

     while(c<''||c>'') { if(c=='-') f=-; c=getchar(); }

     while(''<=c&&c<='') { x=(x<<)+(x<<)+c-''; c=getchar(); }

     return x*f;

 }

 inline void add(int x,int y)

 {

     e[++num].to=y;

     e[num].next=head[x];

     head[x]=num;

 }

 void Tarjan(int u){

     dfn[u]=low[u]=++cnt;

     stack[++top]=u;

     instack[u]=;

     for(int i=head[u];i;i=e[i].next)

      if(!dfn[e[i].to]){

         Tarjan(e[i].to);

         low[u]=min(low[u],low[e[i].to]);

      }

      else if(instack[e[i].to])

       low[u]=min(low[u],dfn[e[i].to]);

     if(low[u]==dfn[u]){

         belong[u]=++tot;

         size[tot]++;　　　　//记录强连通分量大小

         while(stack[top]!=u){

             int t=stack[top];

             belong[t]=tot;

             instack[t]=;

             size[tot]++;

             top--;

         }

         top--;

         instack[u]=;

     }

 }

 int main()

 {

     scanf("%d%d",&n,&m);

     int x,y;

     for(int i=;i<=m;i++){

         x=read(); y=read();

         add(x,y);

     }

     for(int i=;i<=n;i++)

      if(!dfn[i])

       Tarjan(i);

     for(int i=;i<=n;i++)

      for(int j=head[i];j;j=e[j].next)　　//统计出度

       if(belong[i]!=belong[e[j].to])

        du[belong[i]]++;

     int ans=;

     for(int i=;i<=tot;i++)

      if(!du[i]){

          ans=size[i];

          k++;

      }

     if(k==)

      printf("%d\n",ans);

     else puts("");

     return ;

 }