题意：
有N(N<=10000)头牛，每头牛都想成为most poluler的牛，给出M(M<=50000)个关系，如(1,2)代表1欢迎2，关系可以传递，但是不可以相互，即1欢迎2不代表2欢迎1，但是如果2也欢迎3那么1也欢迎3.给出N,M和M个欢迎关系，求被所有牛都欢迎的牛的数量。
/* tarjan缩点后，统计每个所点的出度，当有且只有一个出度为0的缩点是， 答案即为这个缩点所包含的点的数量，否则答案为0 */ #include<cstdio> #include<iostream> #include<cstring> #include<vector> #include<stack> #define M 10010 using namespace std; int low[M],num[M],belong[M],vis[M],instack[M],in[M],out[M],sum[M],indexx,cnt,n,m; vector<int> grap[M]; stack<int> s; void tarjan(int v) { low[v]=num[v]=++indexx; s.push(v); vis[v]=1; instack[v]=1; for(int i=0;i<grap[v].size();i++) { int w=grap[v][i]; if(!vis[w]) { tarjan(w); low[v]=min(low[v],low[w]); } else if(instack[w]) low[v]=min(low[v],num[w]); } int u; if(low[v]==num[v]) { ++cnt; do { u=s.top(); s.pop(); belong[u]=cnt; sum[cnt]++; instack[u]=0; } while(u!=v); } } void work() { for(int i=1;i<=m;i++) { int x,y; scanf("%d%d",&x,&y); grap[y].push_back(x); } for(int i=1;i<=n;i++) if(!vis[i]) tarjan(i); for(int i=1;i<=n;i++) for(int j=0;j<grap[i].size();j++) if(belong[i]!=belong[grap[i][j]]) { in[belong[i]]++; out[belong[grap[i][j]]]++; } int tot=0,p; for(int i=1;i<=cnt;i++) if(!out[i]) { tot++; p=i; } if(tot==1)printf("%d ",sum[p]); else printf("0 "); } int main() { while(scanf("%d%d",&n,&m)==2) { work(); memset(low,0,sizeof(low)); memset(num,0,sizeof(num)); memset(belong,0,sizeof(belong)); memset(vis,0,sizeof(vis)); memset(instack,0,sizeof(instack)); memset(in,0,sizeof(in)); memset(out,0,sizeof(out)); memset(sum,0,sizeof(sum)); for(int i=1;i<=n;i++)grap[i].clear(); while(!s.empty())s.pop(); indexx=0; cnt=0; } }