暴力求闭包的话数据太大会超时，用强连通分量(O(V+E))做，缩点后求出度，如果只有一个连通分量出度为0，答案就是这个连通分量中点的个数
如果强连通分量a出度不为0，假设它与强连通分量b有边，则强连通分量到a无边，那么a中的牛肯定不被所有其他牛喜欢
如果有两个强连通分量a和b的出度不为0，那么a中的牛不被b中的牛喜欢，b中的牛不被a中的牛喜欢，它们都不会是 最受欢迎的牛
代码：
#include<iostream> #include<stack> using namespace std; const int MAX=50005; struct node { int u,v,next; }g[MAX*2]; int dfn[MAX],low[MAX],vis[MAX],inStack[MAX],adj[MAX],belong[MAX]; int e,cnt,index,out[MAX]; stack<int> s; void tarjan(int u) { int v; vis[u]=1; dfn[u]=low[u]=++index; s.push(u); inStack[u]=1; for(int i=adj[u];i!=-1;i=g[i].next) { v=g[i].v; if(!vis[v]) { tarjan(v); low[u]=min(low[u],low[v]); } else if(inStack[v]) low[u]=min(low[u],dfn[v]); } if(dfn[u]==low[u]) { cnt++; do { v=s.top(); s.pop(); belong[v]=cnt; inStack[v]=0; }while(u!=v); } } int main() { int i,j,a,b,vn,en; scanf("%d%d",&vn,&en); e=0; memset(adj,-1,sizeof(adj)); memset(vis,0,sizeof(vis)); memset(inStack,0,sizeof(inStack)); memset(dfn,0,sizeof(dfn)); memset(belong,0,sizeof(belong)); while(en--) { scanf("%d%d",&a,&b); g[e].u=a; g[e].v=b; g[e].next=adj[a]; adj[a]=e++; } cnt=index=0; for(i=1;i<=vn;i++) { if(!dfn[i]) tarjan(i); } int num=0,res; memset(out,0,sizeof(out)); for(i=0;i<e;i++) { if(belong[g[i].u]!=belong[g[i].v]) out[belong[g[i].u]]++; } for(i=1;i<=cnt;i++) { if(out[i]==0) { num++; res=i; } } if(num>1) cout<<0<<endl; else { num=0; for(i=1;i<=vn;i++) { if(belong[i]==res) num++; } cout<<num<<endl; } return 0; }
