题目大意：有n个牛，已知这些牛之间的崇拜关系，崇拜关系是可以传递的，例如：a崇拜b，b崇拜c，那么a崇拜c。问有多少牛被其他所有牛崇拜？
分析：根据崇拜关系建立有向图，已知同属于一个强连通分量的牛互相崇拜，通过求强连通缩点后，若出度为0的点只有一个，那么这一群牛就被其他所有牛崇拜，否则不存在被其他所有牛崇拜的牛。
View Code
#include <stdio.h> #include <string.h> #define N 10001 #define M 50001 int first[N],next[M],v[M]; int rfirst[N],rnext[M],rv[M]; int n,m,e; int vis[N],dfn[N],id[N],cnt,num[N]; int dout[N]; void init() { e=0; memset(first,-1,sizeof(first)); memset(rfirst,-1,sizeof(rfirst)); } void insert(int a,int b) { v[e]=b; next[e]=first[a]; first[a]=e; rv[e]=a; rnext[e]=rfirst[b]; rfirst[b]=e++; } void dfs(int a) { int i,b; vis[a]=1; for(i=first[a];i!=-1;i=next[i]) { b=v[i]; if(!vis[b]) dfs(b); } dfn[cnt++]=a; } void rdfs(int a) { int i,b; vis[a]=1; id[a]=cnt; num[cnt]++; for(i=rfirst[a];i!=-1;i=rnext[i]) { b=rv[i]; if(!vis[b]) rdfs(b); } } void solve() { int i,j,a,b,t; cnt=0; memset(vis,0,sizeof(vis)); for(i=1;i<=n;i++) { if(!vis[i]) dfs(i); } cnt=0; memset(vis,0,sizeof(vis)); memset(num,0,sizeof(num)); for(t=n-1;t>=0;t--) { i=dfn[t]; if(!vis[i]) rdfs(i),cnt++; } memset(dout,0,sizeof(dout)); for(a=1;a<=n;a++) { for(i=first[a];i!=-1;i=next[i]) { b=v[i]; if(id[a]^id[b]) dout[id[a]]++; } } int x=0; for(i=0;i<cnt;i++) { if(!dout[i]) { x++; j=i; } } if(x>1) puts("0"); else printf("%d\n",num[j]); } int main() { int a,b; while(~scanf("%d%d",&n,&m)) { init(); while(m--) { scanf("%d%d",&a,&b); insert(a,b); } solve(); } return 0; }