http://www.lydsy.com/JudgeOnline/problem.php?id=1051
Description
每一头牛的愿望就是变成一头最受欢迎的牛。现在有N头牛，给你M对整数(A,B)，表示牛A认为牛B受欢迎。 这
种关系是具有传递性的，如果A认为B受欢迎，B认为C受欢迎，那么牛A也认为牛C受欢迎。你的任务是求出有多少头
牛被所有的牛认为是受欢迎的。
Input
第一行两个数N,M。 接下来M行，每行两个数A,B，意思是A认为B是受欢迎的（给出的信息有可能重复，即有可
能出现多个A,B）
Output
一个数，即有多少头牛被所有的牛认为是受欢迎的。
思路：求原图的强连通分量，缩点重构图，如果新DAG中仅存在1个出度为0的点，那么答案就是该强连通分量的包含的节点数，如果不存在这样的点或存在多个（存在多个说明不会有牛被所有牛欢迎），那么无解，输出0
#include<iostream>
#include<cstring>
#include<cstdio>
#include<vector>
using namespace std;
;
vector<int> G[maxn],G2[maxn],S;
int n,m,vis[maxn],book[maxn],bcc_nodes[maxn],bcc_count,out_edges[maxn];
void init(){
memset(vis,,sizeof(vis));
memset(book,,sizeof(book));
memset(bcc_nodes,,sizeof(bcc_nodes));
memset(out_edges,,sizeof(out_edges));
bcc_count=;
}
void dfs(int u){
vis[u]=;
;i<G[u].size();i++){
int go=G[u][i];
if(!vis[go]) dfs(go);
}
S.push_back(u);
}
void dfs2(int u){
book[u]=bcc_count;bcc_nodes[bcc_count]++;
;i<G2[u].size();i++){
int go=G2[u][i];
if(!book[go]) dfs2(go);
}
}
int main()
{
scanf("%d %d",&n,&m);
init();
;i<=m;i++){
int a,b;scanf("%d %d",&a,&b);
G[a].push_back(b);
G2[b].push_back(a);
}
;i<=n;i++) if(!vis[i]) dfs(i);
;i>=;i--) if(!book[S[i]]){
++bcc_count;dfs2(S[i]);
}
,ans=;
;i<=n;i++) ;j<G[i].size();j++) if(book[i]!=book[G[i][j]]){
out_edges[book[i]]=;break;
}
;i<=bcc_count;i++) if(!out_edges[i]) k++,ans+=bcc_nodes[i];
) printf("%d",ans);
");
;
}