并查集模板 （洛谷p3367题解）

#include<bits/stdc++.h>
using namespace std;
const int maxn = 10005;
int s[maxn];
void init(){ // 初始化使初始的每个结点都是自己的根结点
for(int i = 1 ; i <= maxn ; i++){
s[i]=i;
}
}
int find_set(int x){ // 找到每个元素的根结点，并且压缩路径使得每个元素直接接在根节点上
return x==s[x]?x:s[x]=find_set(s[x]);
}
void union_set(int x, int y){//将两个根结点不同的根结点连起来
x = find_set(x);
y = find_set(y);
if(x!=y) s[x]=s[y];
}
int main()
{
int n , m ;
int x , y , z;
init();
int ans=0;
scanf(“%d %d”,&n,&m);
while(m–){
scanf(“%d %d %d”,&z,&x,&y);
if(z==1)
union_set(x,y);
else{
x=find_set(x);
y=find_set(y);
if(x==y)
printf(“Y/n”);
else
printf(“N/n”);
}
}
return 0;
}