1051: [HAOI2006]受欢迎的牛
Description
每一头牛的愿望就是变成一头最受欢迎的牛。现在有N头牛，给你M对整数(A,B)，表示牛A认为牛B受欢迎。 这
种关系是具有传递性的，如果A认为B受欢迎，B认为C受欢迎，那么牛A也认为牛C受欢迎。你的任务是求出有多少头
Input
第一行两个数N,M。 接下来M行，每行两个数A,B，意思是A认为B是受欢迎的（给出的信息有可能重复，即有可
Output
Sample Input
Sample Output
HINT
Source
【分析】
SCC缩点，判断出度为0的强联通分量是否<=1，如果是，那么就输出这个SCC的大小，否则ans为0。
1 #include 2 #include 3 #include 4 #include 5 #include 6 #include 7 using namespace std; 8 #define Maxn 10010 9 #define Maxm 5001010 11 int mymin(int x,int y) { return x
sta;30 31 int dfn[Maxn],low[Maxn],scc[Maxn],cl;32 int siz[Maxn],tot;33 bool inst[Maxn];34 void dfs(int x)35 {36 dfn[x]=low[x]=++tot;37 sta.push(x);inst[x]=1;38 for(int i=first[x];i;i=t[i].next) if(t[i].p)39 {40 // t[i].p=t[t[i].o].p=0;41 t[i].p=0;42 int y=t[i].y;43 if(!dfn[y])44 {45 dfs(y);46 low[x]=mymin(low[x],low[y]);47 }48 else if(inst[y]) low[x]=mymin(low[x],dfn[y]);49 }50 if(low[x]==dfn[x])51 {52 cl++;siz[cl]=0;53 while(sta.top()!=x)54 {55 scc[sta.top()]=cl;56 inst[sta.top()]=0;57 sta.pop();58 siz[cl]++;59 }60 scc[x]=cl;siz[cl]++;61 inst[x]=0;62 sta.pop();63 }64 }65 66 int cd[Maxn];67 68 int main()69 {70 int n,m;71 scanf("%d%d",&n,&m);72 for(int i=1;i<=m;i++)73 {74 int x,y;75 scanf("%d%d",&x,&y);76 ins(x,y);77 }78 memset(dfn,0,sizeof(dfn));79 memset(inst,0,sizeof(inst));80 // sta.clear();81 cl=0;tot=0;82 for(int i=1;i<=n;i++) if(!dfn[i])83 {84 dfs(i);85 }86 memset(cd,0,sizeof(cd));87 for(int i=1;i<=m;i++)88 {89 if(scc[t[i].x]==scc[t[i].y]) continue;90 cd[scc[t[i].x]]++;91 }92 int nw=0,id;93 for(int i=1;i<=cl;i++) if(cd[i]==0) nw++,id=i;94 if(nw<=1) printf("%d\n",siz[id]);95 else printf("0\n");96 return 0;97 }
View Code 
