找到x所在集合的最父级代表元素
如果这个集合只有x自己,那么最父级代表元素当然就是它自己
*/
intFindSet(int * p,int x)
{
int tmp,px=x;
while(p[px]>=0) //找到x所在集合的代表元素
px=p[px];
/*
路径压缩,可选,如果需要频繁查询,压缩之后可以提高速度
即把从x到代表元素路径上的所有的元素的父节点都表示为代表元素
*/
while(p[x]>=0)
{
tmp=p[x];
p[x]=px;
x=tmp;
}
return px; //x元素所在集合的代表元素
}
/*
合并x和y所在的集合.
*/
voidUnionSet(int * p,int x,int y)
{
int tmp;
x=FindSet(p,x);
y=FindSet(p,y);
if(x==y)
return ;
tmp=p[x]+p[y];
if(p[x]>p[y]) //将小树合并到大树下
{
p[y]=tmp;
p[x]=y;
}
else
{
p[x]=tmp;
p[y]=x;
}
return ;
}
/*
① 凡本网注明稿件来源为"原创"的所有文字、图片和音视频稿件,版权均属本网所有。任何媒体、网站或个人转载、链接转贴或以其他方式复制发表时必须注明"稿件来源:我考网",违者本网将依法追究责任;
② 本网部分稿件来源于网络,任何单位或个人认为我考网发布的内容可能涉嫌侵犯其合法权益,应该及时向我考网书面反馈,并提供身份证明、权属证明及详细侵权情况证明,我考网在收到上述法律文件后,将会尽快移除被控侵权内容。