题目链接：http://poj.org/problem?id=2186
题目大意：给定N头牛和M个有序对(A,B),(A,B)表示A牛认为B牛是红人，该关系具有传递性，如果牛A认为牛B是红人，牛B认为牛C是红人，那么牛A也认为牛C是红人。求被其他所有牛认为是红牛的牛的总数。
解题思路：把所有牛看成顶点，把有序对（A,B）看成从A到B的有向边，那么题目就变成了求所有顶点都可到达的顶点的总数。我们可以得到一个结论，如果一个强连通分量里有一头牛被认为是红人，那么该强联通分量里的所有牛都是红人，这显然是正确的。由于我用的是Kosaraju求强联通分量，根据该算法性质，红牛只会在拓扑序最后的强联通分量里，我只需要找到最后一块强联通分量，取其中一个顶点，看是否所有点都可以到达即可。
#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
const int N=1e4+; vector<int>G[N];//图的邻接表
vector<int>rG[N];//反向图的邻接表
vector<int>vs;//后序遍历的顺序的顶点列表
bool used[N];//记录点是否被访问
int cmp[N];//cmp[i]表示点i所属强联通分量的拓扑序 int V,E; void addedge(int u,int v){
G[u].push_back(v);
rG[v].push_back(u);
} void dfs(int v){
used[v]=true;
for(int i=;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;
//点v属于第k个强连通分量
cmp[v]=k;
for(int i=;i<rG[v].size();i++){
if(!used[rG[v][i]])
rdfs(rG[v][i],k);
}
} int scc(){
memset(used,false,sizeof(used));
vs.clear();
//第一次DFS
for(int i=;i<=V;i++){
if(!used[i])
dfs(i);
}
memset(used,false,sizeof(used));
int k=;//强联通分量块数
//第二次DFS
for(int i=vs.size()-;i>=;i--){
if(!used[vs[i]])
rdfs(vs[i],++k);
}
return k;
} void solve(){
//获得强联通块数
int n=scc();
//统计备选解的个数
int u=,num=;
for(int i=;i<=V;i++){
if(cmp[i]==n){
u=i;
num++;
}
}
//检查是否所有点可达
memset(used,,sizeof(used));
rdfs(u,); for(int i=;i<=V;i++){
if(!used[i]){
num=;
break;
}
}
for(int i=;i<=V;i++){
cout<<"i="<<i<<" cmp="<<cmp[i]<<endl;
}
printf("%d\n",num);
} int main(){
scanf("%d%d",&V,&E);
for(int i=;i<=E;i++){
int u,v;
scanf("%d%d",&u,&v);
addedge(u,v);
}
solve();
return ;
}