题目链接：http://poj.org/problem?id=2186
挑战程序设计竞赛P322
题目大意：
每头牛都想成为牛群中的红人。给定N头牛的牛群和M个有序对（A， B）。（A， B）表示牛A认为牛B是红人。该关系具有传递性，所以如果牛A认为牛B是红人，牛B认为牛C是红人，那么牛A也认为牛C是红人。不过，给定的有序对中可能包含（A，B）和（B，C），但不包含(A,C)。求被其他所有牛认为是红人的牛的总数。
分析：
需要掌握Kosaraju求得的强连通分量满足拓扑序，具体解释请看挑战程序设计竞赛。
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<vector>
using namespace std;
const int max_v = 100005;
int N, M;
int V;
vector<int> G[max_v];
vector<int> rG[max_v];
vector<int> vs;
bool used[max_v];
int cmp[max_v];
void add_edge(int from, int to)
{G[from].push_back(to);rG[to].push_back(from);
}
void dfs(int u)
{used[u] = true;for(int i = 0; i < G[u].size(); i++)if(!used[G[u][i]])dfs(G[u][i]);vs.push_back(u);
}
void rdfs(int u, int k)
{used[u] = true;cmp[u] = k;for(int i = 0; i < rG[u].size(); i++)if(!used[rG[u][i]])rdfs(rG[u][i], k);
}
int src()
{memset(used, 0, sizeof(used));vs.clear();for(int u = 0; u < V; u++)if(!used[u])dfs(u);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 main()
{while(cin >> N >> M){V = N;for(int i = 0; i <= N-1; i++){if(!G[i].empty())G[i].clear();if(!rG[i].empty())rG[i].clear();}for(int i = 0; i < M; i++){int u, v;cin >> u >> v;add_edge(u-1, v-1);}int n = src();int u = 0, num = 0;for(int v = 0; v < V; v++)if(cmp[v] == n-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;}cout << num << endl;}return 0;
}