POJ 2186 Popular Cows

 1 #include<iostream>
 2 #include<cstring>
 3 #include<cstdio>
 4 #include<stack>
 5 #define maxn 10005
 6 #define maxm 50010
 7 using namespace std;
 8 int n,m;
 9 struct edge{
10     int u,v,next;
11 }e[maxm],ee[maxm];
12 int head[maxn],js,headd[maxn],jss,bianshu;
13 bool exist[maxn];
14 int visx,cur;// cur--缩出的点的数量 
15 int dfn[maxn],low[maxn],belong[maxn],chudu[maxn],rudu[maxn];
16 stack<int>st;
17 void add_edge(int u,int v){
18     e[++js].u=u;e[js].v=v;
19     e[js].next=head[u];head[u]=js;
20 }
21 void add_edgee(int u,int v){
22     ee[++jss].u=u;ee[jss].v=v;
23     ee[jss].next=head[u];head[u]=jss;
24 }
25 void tarjan(int u){
26     dfn[u]=low[u]=++visx;
27     st.push(u);exist[u]=true;
28     for(int i=head[u];i;i=e[i].next){
29         int v=e[i].v;
30         if(dfn[v]==0) {
31             tarjan(v);
32             low[u]=min(low[v],low[u]);
33         }
34         else if(exist[v]&&low[u]>dfn[v]) low[u]=dfn[v];
35     }
36     int j;
37     if(low[u]==dfn[u]){
38         ++cur;
39         do{
40             j=st.top();st.pop();
41             exist[j]=false;belong[j]=cur;
42             rudu[cur]++;
43         }while(j!=u);
44     }
45 }
46 int main()
47 {
48     scanf("%d%d",&n,&m);
49     int u,v;
50     for(int i=1;i<=m;i++){
51         scanf("%d%d",&u,&v);
52         add_edge(u,v);
53     }
54     for(int i=1;i<=n;i++)
55       if(dfn[i]==0)
56         tarjan(i);      
57     for(int i=1;i<=js;i++){
58         int u=e[i].u,v=e[i].v;
59         if(belong[u]!=belong[v]){
60             add_edgee(belong[u],belong[v]);
61             chudu[belong[u]]++;
62         }
63     }
64     int chu=0,ru=0;
65     for(int i=1;i<=cur;i++){
66         if(chudu[i]==0) chu++,bianshu=i;
67     }
68     if(chu==1) printf("%d\n",rudu[bianshu]);
69     else printf("%d\n",0);
70     return 0;
71 }