```cpp
void Union(int root1, int root2)
{
int temp = a[root1] + a[root2];
if(a[root2] < a[root1]) {
a[root1] = root2;
a[root2] = temp;
}
else {
a[root2] = root1;
a[root1] = temp;
}
}
```
冒昧的问一句,请问您为什么要新建一个节点呢??
by Lupus @ 2019-07-23 15:00:10
@[焦铭扬](/space/show?uid=183629) 主函数没问题 合并和查找的函数貌似都有问题
by Raw_Aya9285 @ 2019-07-23 15:03:42
诶不对 好像主函数也有问题
by Raw_Aya9285 @ 2019-07-23 15:04:34
@[焦铭扬](/space/show?uid=183629)
find部分只用简单地判断:
```cpp
if(a[x]!=x){ //如果祖先不是本身
a[x]=find(a[x]); //就继续找祖先
}
return a[x]; //返回祖先
```
这样就可以了。
为了配合这段函数,主函数的初始化应该是这样:
```
for(int i=1;i<=n;i++){
a[i]=i; //一开始每个人的祖先都是自己
}
```
另外合并函数内也只需要简单判断是否相同就可以了,大概如下:
```cpp
int r1=find(root1),r2=find(root2);
if(r1!=r2){
a[r2]=r1;
}
```
by Raw_Aya9285 @ 2019-07-23 15:12:05
@[__fishsause__](/space/show?uid=185527)
我的并查集是每个的根节点存的是这个树元素的个数的复数,子节点存的是其父节点的下标,一开始每个人的祖先都是自己,所以都制成-1,而我第二个find函数是为了路径优化。我只过了4个,剩下的都是RE
by Clover_INF @ 2019-07-23 15:19:39