[USACO03FALL][HAOI2006]受欢迎的牛 G

  1 #include<bits/stdc++.h>
  2 
  3 using namespace std;
  4 const int mmm=5e4+5;
  5 
  6 int n,m;
  7 int a[mmm],head[mmm],nxt[mmm],to[mmm];
  8 int cnt;
  9 
 10 void add(int x,int y)
 11 {
 12     cnt++;
 13     to[cnt]=y;
 14     nxt[cnt]=head[x];
 15     head[x]=cnt;
 16     return ;
 17 }
 18 
 19 int tot,sum;
 20 int low[mmm],dep[mmm],id[mmm],flag[mmm],siz[mmm];
 21 stack <int >s; 
 22 void dfs(int x)
 23 {
 24     tot++;
 25     dep[x]=tot;    
 26     low[x]=tot;
 27     s.push(x);
 28     flag[x]=1;
 29     for(int i=head[x];i;i=nxt[i])
 30     {
 31         int y=to[i];
 32         if(!dep[y])
 33         {
 34             dfs(y);
 35             low[x]=min(low[x],low[y]);
 36         }
 37         else if(flag[y])
 38         {
 39             low[x]=min(low[x],low[y]);
 40         }
 41     }
 42     int k;
 43     if(low[x]==dep[x])
 44     {
 45          sum++;
 46         do
 47         {
 48         k=s.top();
 49         s.pop();    
 50             siz[sum]++;
 51             flag[k]=0;
 52             id[k]=sum;
 53         
 54         }while(k!=x);
 55         
 56     }
 57     return ;    
 58 }
 59 
 60 int main()
 61 {
 62     ios::sync_with_stdio(false);    
 63     cin>>n>>m;
 64     for(int i=1;i<=m;i++)
 65     {
 66         int q,w;    
 67         cin>>q>>w;
 68         add(w,q);
 69     }
 70 
 71     for(int i=1;i<=n;i++)
 72     {
 73         if(!dep[i])
 74         dfs(i);
 75     }
 76     for(int i=1;i<=n;i++)
 77     {
 78         for(int j=head[i];j;j=nxt[j])
 79         {
 80             int y=to[j];
 81            if(id[i]!=id[y])
 82            a[id[y]]++;
 83         }
 84     }
 85     int ans=0;
 86     for(int i=1; i<=sum; ++i)
 87     {
 88         if(!a[i])   
 89         {
 90             if(ans) 
 91             {
 92             cout<<0; return 0;
 93             }
 94             ans=i;
 95         }
 96     }
 97     cout<<siz[ans];
 98  
 99     return 0;
100  }