POJ.2186 Popular Cows

1.Problem
2186 -- Popular Cows (poj.org)

2.Idea
SCC+Topological Sort

3.Source

 const int N = 100005;  
 //////////////////////////////  
 int V;  
 vector<int> G[N];  
 vector<int> rG[N];  
 vector<int> vs;  
 bool used[N];  
 int cmp[N];  
 void add_edge(int from, int to)  
 {  
      G[from].push_back(to);  
      rG[to].push_back(from);  
 }  
 void dfs(int v)  
 {  
      used[v] = true;  
      for (int i = 0; i < G[v].size(); i++) {  
           if (!used[G[v][i]]) dfs(G[v][i]);  
      }  
      vs.push_back(v);  
 }  
 void rdfs(int v, int k)  
 {  
      used[v] = true;  
      cmp[v] = k;  
      for (int i = 0; i < rG[v].size(); i++) {  
           if (!used[rG[v][i]]) rdfs(rG[v][i], k);  
      }  
 }  
 int scc()  
 {  
      memset(used, 0, sizeof used);  
      vs.clear();  
      for (int v = 0; v < V; v++) {  
           if (!used[v]) dfs(v);  
      }  
      memset(used, 0, sizeof used);  
      int k = 0;  
      for (int i = vs.size() - 1; i >= 0; i--) {  
           if (!used[vs[i]]) rdfs(vs[i], k++);  
      }  
      return k;  
 }  
 int n, m;  
 int a[N], b[N];  
 void solve()  
 {  
      scanf("%d%d", &n, &m);  
      REP(i, m) scanf("%d%d", &a[i], &b[i]);  
      V = n;  
      for (int i = 0; i < m; i++) {  
           add_edge(a[i] - 1, b[i] - 1);  
      }  
      int nn = scc();  
      int u = 0, num = 0;  
      for (int v = 0; v < V; v++) {  
           if (cmp[v] == nn - 1) {  
                u = v;  
                num++;  
           }  
      }  
      memset(used, 0, sizeof(used));  
      rdfs(u, 0);  
      for (int v = 0; v < V; v++) {  
           if (!used[v]) {  
                num = 0;  
                break;  
           }  
      }  
      printf("%d\n", num);  
 }