poj 2186 Popular Cows

  1 #include <cstdio>
  2 #include <cstring>
  3 #include <algorithm>
  4 #include <vector>
  5 #include <stack>
  6 #define maxn 100001
  7 using namespace std;
  8 
  9 int dfn[maxn],low[maxn],belong[maxn],bcnt,bcc_clock,a[maxn],b[maxn],num[maxn],n,m,head[maxn],e;
 10 stack<int>s;
 11 bool vis[maxn],flag[maxn];
 12 struct node
 13 {
 14     int v,next;
 15 }p[maxn];
 16 
 17 
 18 void add(int u,int v)
 19 {
 20     p[e].v=v;
 21     p[e].next=head[u];
 22     head[u]=e++;
 23 }
 24 void tarjan(int u)
 25 {
 26     dfn[u]=low[u]=++bcc_clock;
 27     vis[u]=true;
 28     s.push(u);
 29     for(int i=head[u]; i!=-1; i=p[i].next)
 30     {
 31         int v=p[i].v;
 32         if(!dfn[v])
 33         {
 34             tarjan(v);
 35             low[u]=min(low[u],low[v]);
 36         }
 37         else if(vis[v]&&dfn[v]<low[u])
 38         low[u]=dfn[v];
 39     }
 40     if(dfn[u]==low[u])
 41     {
 42         bcnt++;
 43         int j;
 44         do
 45         {
 46             j=s.top();
 47             s.pop();
 48             vis[j]=false;
 49             belong[j]=bcnt;
 50         }while(j!=u);
 51     }
 52 }
 53 
 54 void deal()
 55 {
 56     while(!s.empty())
 57     {
 58         s.pop();
 59     }
 60     memset(dfn,0,sizeof(dfn));
 61     bcnt=0;bcc_clock=0;
 62     for(int i=1; i<=n; i++)
 63     {
 64         if(!dfn[i])
 65         {
 66             tarjan(i);
 67         }
 68     }
 69 }
 70 
 71 void inti()
 72 {
 73     e=0;
 74     memset(head,-1,sizeof(head));
 75     memset(belong,0,sizeof(belong));
 76     memset(low,0,sizeof(low));
 77     memset(a,0,sizeof(a));
 78     memset(b,0,sizeof(b));
 79     memset(num,0,sizeof(num));
 80     memset(flag,false,sizeof(flag));
 81     memset(vis,false,sizeof(vis));
 82 }
 83 
 84 int main()
 85 {
 86     while(scanf("%d%d",&n,&m)!=EOF)
 87     {
 88         inti();
 89         for(int i=1; i<=m; i++)
 90         {
 91             scanf("%d%d",&a[i],&b[i]);
 92             add(a[i],b[i]);
 93         }
 94         deal();
 95         for(int i=1; i<=m; i++)
 96         {
 97             if(belong[a[i]]!=belong[b[i]])
 98                 flag[belong[a[i]]]=true;
 99         }
100         for(int i=1; i<=n; i++)
101         {
102             num[belong[i]]++;
103         }
104         int t=0,ans;
105         for(int i=1; i<=bcnt; i++)
106         {
107             if(!flag[i])
108             {
109                 t++;
110                 ans=num[i];
111             }
112         }
113         if(t==1)
114             printf("%d
",ans);
115         else
116             printf("0
");
117     }
118     return 0;
119 }
View Code