Popular Cows

  1 #include<iostream>
  2 #include<cstdio>
  3 #include<cstring>
  4 
  5 using namespace std;
  6 
  7 #define N 10008
  8 
  9 int Time, cnt, tot, top;
 10 int dfn[N], low[N], instack[N], stackk[N], head[N];
 11 int vis[N], id[N];
 12 
 13 struct node
 14 {
 15     int u, v, next;
 16 }e[N*5];   // 邻接表
 17 
 18 void add(int a, int b)
 19 {
 20     e[cnt].u = a;
 21     e[cnt].v = b;
 22     e[cnt].next = head[a];
 23     head[a] = cnt;
 24     cnt++;
 25 }
 26 
 27 void init()
 28 {
 29     tot = cnt = top = 0;
 30     Time = 0;
 31     memset(dfn, 0, sizeof(dfn));
 32     memset(low, 0, sizeof(low));
 33     memset(instack, 0, sizeof(instack));
 34     memset(stackk, 0, sizeof(stackk));
 35     memset(head, -1, sizeof(head));
 36     memset(vis, 0, sizeof(vis));
 37     memset(id, 0, sizeof(id));
 38 }
 39 
 40 void Tarjan(int u)
 41 {
 42     low[u] = dfn[u] = ++Time;
 43     instack[u] = 1;
 44     stackk[top++] = u;
 45 
 46     for(int i = head[u]; i != -1; i = e[i].next)
 47     {
 48         int v = e[i].v;
 49         if(!dfn[v])
 50             Tarjan(v);
 51         if(instack[v])
 52             low[u] = min(low[v], low[u]);
 53     }
 54     int v;
 55     if(low[u] == dfn[u])  // 找到一个连通分量
 56     {
 57         tot++;  // 强连通分量计数
 58         do
 59         {
 60             v = stackk[--top];
 61             instack[v] = 0;
 62             id[v] = tot;
 63         }while(v != u);
 64     }
 65 }
 66 
 67 int main()
 68 {
 69     int n, m, x, y;
 70     while(~scanf("%d%d", &n, &m))
 71     {
 72         init();
 73         while(m--)
 74         {
 75             scanf("%d%d", &x, &y);
 76             add(x, y);
 77         }
 78         for(int i = 1; i <= n; i++)
 79         {
 80             if(!dfn[i])
 81                 Tarjan(i);
 82         }
 83         int sum = 0, x;
 84 
 85         for(int i = 1; i <= n; i++)
 86         {
 87             for(int j = head[i]; j != -1; j = e[j].next)
 88             {
 89                 int q = e[j].v;
 90                 if(id[i] != id[q])  // 如果这两个点不属于一个强连通分量，就把 i 所在强连通分量的出度加一
 91                 {
 92                     vis[id[i]]++;
 93                 }
 94             }
 95         }
 96         for(int i = 1; i <= tot; i++)
 97         {
 98             if(!vis[i])
 99             {
100                 sum++;
101                 x = i;  // 记录哪个强连通分量是出度为0的图
102             }
103         }
104         if(sum == 1)
105         {
106             sum = 0;
107             for(int i = 1; i <= n; i++)
108             {
109                 if(id[i] == x)  // 出度为0的连通分量内的点计数
110                     sum++;
111             }
112             printf("%d\n", sum);
113         }
114         else
115             printf("0\n");
116     }
117     return 0;
118 }