poj 2186 强连通+缩点

题意：有一群牛，求被所有牛都认可的牛的个数

每个连通分量建一个缩点，出度为零的缩点包含的点的个数即为要求值

如果有多个出度为零的，直接输出零，否则输出那唯一一个出度为零的缩点包含的点的个数

#include<stdio.h>
#include<string.h>
#define N 11000
int dfn[N],low[N],sta[N],visit[N],suo[N],ans,outdegree[N],top,num[N];
int head[N],yong,n,m;
struct node {
int  v,next;
}bian[N*10];
void init() {
   memset(sta,0,sizeof(sta));
   ans=0;
   memset(outdegree,0,sizeof(outdegree));
   memset(suo,0,sizeof(suo));
   memset(dfn,0,sizeof(dfn));
   memset(low,0,sizeof(low));
   memset(visit,0,sizeof(visit));yong=0;top=0;
   memset(head,-1,sizeof(head));
   memset(num,0,sizeof(num));
}
void addedge(int u,int v){
bian[yong].v=v;
bian[yong].next=head[u];
head[u]=yong++;
}
int Min(int u,int v) {
return u>v?v:u;
}
void tarjan(int u) {
visit[u]=1;
dfn[u]=++yong;
low[u]=yong;
sta[++top]=u;
int i,v;
for(i=head[u];i!=-1;i=bian[i].next) {
        v=bian[i].v;
    if(!dfn[v]) {
        tarjan(v);
        low[u]=Min(low[u],low[v]);
    }
    else
        if(visit[v]==1)
        low[u]=Min(low[u],dfn[v]);

}
int coun=0;
if(dfn[u]==low[u]) {
    ans++;
    do{
          v=sta[top--];
          coun++;
          visit[v]=2;
          suo[v]=ans;//缩点
    }while(v!=u);
    num[ans]=coun;//记录缩点包含的点的个数
}
}
int main() {
   int i,j,a,b;
   while(scanf("%d%d",&n,&m)!=EOF) {
        init();
        while(m--) {
            scanf("%d%d",&a,&b);
            addedge(a,b);
        }
          ans=0;
          yong=0;
          for(i=1;i<=n;i++)
            if(visit[i]!=2)
          tarjan(i);
        /*  for(i=1;i<=n;i++)
            printf("%d
",suo[i]);*/
          for(i=1;i<=n;i++)
          for(j=head[i];j!=-1;j=bian[j].next)
          if(suo[i]!=suo[bian[j].v])
                    outdegree[suo[i]]++;
                    yong=0;
          for(i=1;i<=ans;i++)
          if(outdegree[i]==0){
                yong++;
                j=i;
          }
          if(yong>1)
            printf("0
");
          else
            printf("%d
",num[j]);
   }
return 0;
}