poj 2553强连通+缩点

/*先吐槽下，刚开始没看懂题，以为只能是一个连通图0T0

 题意：给你一个有向图，求G图中从v可达的所有点w，也都可以达到v，这样的v称为sink.求这样的v.

 解;求强连通+缩点。求所有出度为0的点即为要求的点。

 注意：可能有多个联通分支。

*/

#include<stdio.h>

#include<string.h>

#include<stdlib.h>

#define N  5100

struct node {

 int u,v,w,next;

}bian[N*N*2];

int head[N],yong,cnt,vis[N],stac[N],top,index,n,low[N],dfn[N],belong[N],outdegree[N];

void addedge(int u,int v) {

    bian[yong].u=u;

    bian[yong].v=v;

    bian[yong].next=head[u];

    head[u]=yong++;

}

int cmp(const void *a,const void *b) {

return *(int *)a-*(int *)b;

}

void init() {

yong=0;

memset(head,-1,sizeof(head));

top=0;cnt=0;

index=0;

memset(vis,0,sizeof(vis));

memset(stac,0,sizeof(stac));

memset(outdegree,0,sizeof(outdegree));

memset(low,0,sizeof(low));

memset(dfn,0,sizeof(dfn));

memset(belong,0,sizeof(belong));

}

int Min(int a,int b) {

return a>b?b:a;

}

void tarjan(int u) {

  low[u]=dfn[u]=++index;

  stac[++top]=u;

  vis[u]=1;

  int i;

  for(i=head[u];i!=-1;i=bian[i].next) {

    int v=bian[i].v;

    if(!dfn[v]) {

        tarjan(v);

        low[u]=Min(low[u],low[v]);

    }

    else

    if(vis[v])

        low[u]=Min(low[u],dfn[v]);

  }

  if(low[u]==dfn[u]){

    cnt++;

    int t;

    do {

        t=stac[top--];

        belong[t]=cnt;

        vis[t]=0;

    }while(t!=u);

  }

}

int main() {

   int m,i,a,b,j;

   while(scanf("%d",&n),n) {

        init();

    scanf("%d",&m);

    while(m--) {

        scanf("%d%d",&a,&b);

        addedge(a,b);

    }

    for(i=1;i<=n;i++)//缩点

    if(!dfn[i])

    tarjan(i);

    //printf("%d\n",cnt);

    for(i=0;i<yong;i++) {

    a=bian[i].u;

    b=bian[i].v;

    if(belong[a]!=belong[b])

        outdegree[belong[a]]++;

    }

    top=0;

    for(i=1;i<=cnt;i++)

        if(outdegree[i]==0) {//找出度为0的点

     for(j=1;j<=n;j++)

        if(belong[j]==i)

        stac[top++]=j;

        }

        qsort(stac,top,sizeof(int),cmp);//排序

     for(i=0;i<top-1;i++)//

        printf("%d ",stac[i]);

     printf("%d\n",stac[top-1]);

   }

return 0;

}
巴特西

poj 2553强连通+缩点

最新文章

热门文章
