2018-07-18-连通图&邻接多重表
2018-07-19 本文已影响0人
termanary
题目: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;
}