CSP_JAKME @ 2024-08-25 19:00:54
#include<bits/stdc++.h>
using namespace std;
int n,q,f[10001];
int get(int x){
if(f[x]==x) return x;
return get(f[x]);
}
int main(){
cin >> n >> q;
for(int i=1;i<=n;i++) f[i]=i;
while(q--){
int x,y,z;
cin >> z >> x >> y;
if(z==1){
if(get(x)!=get(y)) f[y]=x;
}else{
if(get(x)==get(y)) cout << "Y" << endl;
else cout << "N" << endl;
}
}
return 0;
}by chzhh_111 @ 2024-08-25 19:08:59
如果你要合并两个并查集的话，请将一个并查集的代表赋值为另外一个并查集的代表，也就是可以理解为在他们这两个的并查集的代表之间连一条边，而不是他们之间连一条边。
如下：
if(z==1&&get(x)!=get(y))f[get(y)]=get(x);而且最好使用路径压缩等优化技巧，要不然可能会被构造数据整超时。
路径压缩：
就是在查询这个元素所在的并查集的代表的时候，直接将这个并查集的所有节点都连向代表。如下：
int get(int x)
{
if(f[x]==x) return x;
return f[x]=get(f[x]);
}by chzhh_111 @ 2024-08-25 19:09:56
可能表述不是很清楚，具体请看代码。
by chzhh_111 @ 2024-08-25 19:11:27
@CSP_JAKME