poj2186Popular Cows（强连通分量）

用tarjan算出强连通分量的个数将其缩点连成一棵树则题目所求即变成求出度为0 的那个节点在树中是唯一的即树根
  1 #include <iostream>
  2  #include<cstdio>
  3  #include<cstring>
  4  #include<algorithm>
  5  #include<stdlib.h>
  6  #include<stack>
  7  using namespace std;
  8  #define M 50010
  9  #define N 10010
 10  struct node
 11  {
 12      int u,v,next;
 13  }edge[M*2];
 14  int head[N],lowlink[N],pre[N],t,sccno[N],scc,dep,dout[N];
 15  stack<int>s;
 16  void init()
 17  {
 18      t = 0;
 19      memset(head,-1,sizeof(head));
 20      memset(lowlink,0,sizeof(lowlink));
 21      memset(pre,0,sizeof(pre));
 22      memset(sccno,0,sizeof(sccno));
 23      dep=0;scc=0;
 24  }
 25  void add(int u,int v)
 26  {
 27      edge[t].u = v;
 28      edge[t].v = v;
 29      edge[t].next = head[u];
 30      head[u] = t++;
 31  }
 32  void dfs(int u)
 33  {
 34      lowlink[u] = pre[u] = ++dep;
 35      s.push(u);
 36      for(int i = head[u] ; i != -1 ; i = edge[i].next)
 37      {
 38          int v = edge[i].v;
 39          if(!pre[v])
 40          {
 41              dfs(v);
 42              lowlink[u] = min(lowlink[u],lowlink[v]);
 43          }
 44          else if(!sccno[v])
 45          lowlink[u] = min(lowlink[u],pre[v]);
 46      }
 47      if(lowlink[u]==pre[u])
 48      {
 49          scc++;
 50          for(;;)
 51          {
 52              int x = s.top();s.pop();
 53              sccno[x] = scc;
 54              if(x==u) break;
 55          }
 56      }
 57  }
 58  void find_scc(int n)
 59  {
 60      for(int i = 1 ; i <= n  ; i++)
 61      if(!pre[i]) dfs(i);
 62  }
 63  int main()
 64  {
 65      int i,j,n,m,a,b;
 66      while(cin>>n>>m)
 67      {
 68          init();
 69          while(m--)
 70          {
 71              cin>>a>>b;
 72              add(a,b);
 73          }
 74          find_scc(n);
 75          for(i = 1; i <= scc ; i++)
 76          dout[i] = 0;
 77          for(i = 1; i <= n ; i++)
 78              for(j = head[i] ; j!=-1 ; j = edge[j].next)
 79              {
 80                  int v = edge[j].v;
 81                  if(sccno[i]!=sccno[v])
 82                      dout[sccno[i]] = 1;
 83              }
 84          int num=0,o,w=0;
 85          for(i = 1 ; i <= scc ; i++)
 86              if(dout[i]==0)
 87              {
 88                  o = i;
 89                  num++;
 90              }
 91          if(num==0)
 92          cout<<n<<endl;
 93          else if(num==1)
 94          {
 95              for(i = 1; i <= n ; i++)
 96              if(sccno[i]==o)
 97              {
 98                 w++;
 99              }
100              cout<<w<<endl;
101          }
102          else
103          cout<<"0
";
104      }
105      return 0;
106  }
View Code