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\n",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\n");

          else

            printf("%d\n",num[j]);

   }

return 0;

}

巴特西

poj 2186 强连通+缩点

最新文章

热门文章