hdu 3836 强连通+缩点：加边构强连通

#include<stdio.h>//求出其所有的强连通分量缩点，选出出度和入度最大的那个就是要求的边

#include<string.h>

#include<stdlib.h>

#define N 51000

struct node {

 int v,next;

}bian[N];

int head[N],yong,n,indegree[N],outdegree[N],visit[N],suo[N],dfn[N],f,low[N],index,stac[N],top;

void addedge(int u,int v) {

bian[yong].v=v;

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

head[u]=yong++;

}

void init() {

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

    yong=0;index=0,top=0;f=0;

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

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

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

memset(indegree,0,sizeof(indegree));

memset(visit,0,sizeof(visit));

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

}

int Min(int a,int b) {

return a>b?b:a;

}

int MAX(int a,int b) {

return a>b?a:b;

}

void tarjan(int u) {

    int v,i;

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

    visit[u]=1;

    stac[++top]=u;

    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]);

    }

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

        f++;

        int v;

        do{

            v=stac[top--];

            visit[v]=2;

            suo[v]=f;

        }while(v!=u);

    }

}

int main() {

    int m,i,j,fin,fou,v;

    while(scanf("%d%d",&n,&m)!=EOF) {

            if(m==0) {

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

                continue;

            }

               init();

        while(m--) {

            scanf("%d%d",&i,&j);

            addedge(i,j);

        }

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

            if(visit[i]!=2)

        tarjan(i);

            if(f==1) {//判断是否已经是一个联通图

                printf("0\n");

                continue;

            }

       // printf("1\n");

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

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

            v=bian[j].v;

          //  printf("%d %d\n",suo[i],suo[v]);

            if(suo[i]!=suo[v]) {

                indegree[suo[v]]++;

            outdegree[suo[i]]++;

            }

        }

        fin=0;fou=0;

        for(i=1;i<=f;i++) {

            if(indegree[i]==0)

               fin++;

               if(outdegree[i]==0)

                fou++;

        }

        printf("%d\n",MAX(fin,fou));

    }

return 0;

}
巴特西

hdu 3836 强连通+缩点：加边构强连通

最新文章

热门文章
