2018-07-18-连通图&邻接多重表

题目：HDOJ-1232

代码：（用邻接多重表求连通图个数）

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>

typedef struct graph
{
    int v1,v2;
    struct graph *n1,*n2;
}*gra;

gra *p;
int n,m;

int dfs(const int fi)
{
    gra tmp,cn;
    int se;
    tmp=p[fi];
    if(tmp==NULL)
        return 0;
    for(;tmp!=NULL;tmp=p[fi])
    {
        p[fi]=fi==tmp->v1?tmp->n1:tmp->n2;
        se=fi!=tmp->v1?tmp->v1:tmp->v2;
        if(tmp->v1!=tmp->v2)
        {
            cn=p[se];
            for(;cn!=NULL&&(se==cn->v1?cn->n1:cn->n2)!=tmp;)
            {
                cn=se==cn->v1?cn->n1:cn->n2;
            }
            if(cn==NULL)
            {
                p[se]=se==p[se]->v1?p[se]->n1:p[se]->n2;
            }
            else
            {
                if(cn->n1==tmp)
                {
                    cn->n1=(se==tmp->v1?tmp->n1:tmp->n2);
                }
                else
                {
                    cn->n2=(se==tmp->v1?tmp->n1:tmp->n2);
                }
            }
        }
        free(tmp);
        dfs(se);
    }
    return 1;
}

int main()
{
    while( scanf("%d",&n)&&n!=0 )
    {
        int i;
        gra tmp,sa;
        p=(gra*)calloc(n+1,sizeof(gra));
        assert(p);
        scanf("%d",&m);
        for(i=0;i<m;i++)
        {
            tmp=(gra)calloc(1,sizeof(struct graph));
            assert(tmp);
            scanf("%d%d",&tmp->v1,&tmp->v2);
            if(tmp->v1>tmp->v2)
            {
                tmp->v1=tmp->v1^tmp->v2;
                tmp->v2=tmp->v1^tmp->v2;
                tmp->v1=tmp->v1^tmp->v2;
            }
            for(sa=p[tmp->v1]; sa!=NULL && sa->v2!=tmp->v2 ;sa=tmp->v1==sa->v1?sa->n1:sa->n2);
            if(sa!=NULL)
            {
                free(tmp);
            }
            else
            {
                tmp->n1=p[tmp->v1];
                p[tmp->v1]=tmp;
                tmp->n2=p[tmp->v2];
                p[tmp->v2]=tmp;
            }
        }
        for(i=1;i<=n;i++)
        {
            for(tmp=p[i];tmp!=NULL && tmp->v1!=tmp->v2 ;tmp=i==tmp->v1?tmp->n1:tmp->n2);
            if(tmp==NULL)
            {
                tmp=(gra)calloc(1,sizeof(struct graph));
                assert(tmp);
                tmp->v1=tmp->v2=i;
                tmp->n2=tmp->n1=p[tmp->v1];
                p[i]=tmp;
            }
        }
        int cnt;
        gra tr;
        for(i=1,cnt=0;i<=n;i++)
        {
            cnt+=dfs(i);
        }
        printf("%d\n",cnt-1);
    }
    return 0;
}