做并查集时有三个步骤,即:初始化(makeset)——>查找根(findset)——>合并集合(union)。只要掌握了这三步,一些简单的并查集也就差不多OK了。
一、初始化:
官方点的话说就是把每个点所在的集合初始化为其自身。
这个不难,就直接把代码贴上:
void makeset(int x)
{
int i;
for(i=1;i<=x;x++)
{
p[i]=i;        /*数组p[x]表示x的老爸的编号*/
r[i]=1;
}
}
二、查找(我们也可以叫做”寻根”):
官方说法:查找元素所在集合。
这个查找返回的是该元素的根,返回用int型。
int findset(int x)
{
if(x!=p[x])
p[x]=findset(p[x]);
return p[x];
}
三、合并(压缩路径)
官方:将两个元素所在的集合合并为一个集合,但合并之前,应先判断两个元素是否属于同一集合。
原则是:合并时将元素所在深度低的集合合并到元素所在深度深的集合。
可以画图理解一下:

0_1325747352lfCO0_1325747364Eqo8

void union(int x,int y)
{
int fx=findset(x);
int fy=findset(y);
if(fx!=fy)
{
if(fx<fy)
{
p[fy]=fx;
r[fx]+=r[fy];
r[fy]=0;
}
else
{
p[fx]=fy;
r[fy]+=r[fx];
r[fx]=0;
}
}
}

 

A题解:
#include
int p[1000],r[1000];
void makeset(int m) /*初始化*/
{
int i;
for(i=1;i<=m;i++)
{
p[i]=i;
r[i]=1;
}
}
int findset(int x) /*查*/
{
if(x!=p[x])
p[x]=findset(p[x]);
return p[x];
}
void Union(int x,int y) /*并*/
{
int fx=findset(p[x]);
int fy=findset(p[y]);
if(fx!=fy)
{
if(fx<fy)
{
p[fy]=fx;
r[fx]+=r[fy];
r[fy]=0;
}
else
{
p[fx]=fy;
r[fy]+=r[fx];
r[fx]=0;
}
}
}
int main()
{
int T;
int m,n,x,y;
int i;
scanf(“%d”,&T);
while(T –)
{
int ans=0;
scanf(“%d %d”,&m,&n);
makeset(m);
for(i=0;i<n;i++)
{
scanf(“%d %d”,&x,&y);
Union(x,y);
}
for(i=1;i<=m;i++) if(r[i]>0)
ans++;
printf(“%d\n”,ans);
}
return 0;
}

发表评论

电子邮件地址不会被公开。

Post Navigation