并查集模板题----P3367 【模板】并查集

4 7
2 1 2
1 1 2
2 1 2
1 3 4
2 1 4
1 2 3
2 1 4  

N
Y
N
Y
  

#include <iostream>
using namespace std;
const int NN = 1e6+10;
int N,M;
int fa[NN];

int find(int x){ //查询，并压缩路径
    if(x != fa[x])
        fa[x] = find(fa[x]);
    return fa[x];
}

void join(int x,int y){ //合并x，y所在的集合
    int fx = find(x),fy = find(y);
    if(fx != fy)
        fa[fx] = fy;
}

int main(){
    cin>>N>>M;
    for(int i = 1;i<=N;i++) fa[i] = i;//初始化每个结点的祖先是自己
    int op,t1,t2;
    while(M--){
        scanf("%d%d%d",&op,&t1,&t2);
        if(op == 1){
            join(t1,t2); //合并
        }else{
            if(find(t1) == find(t2)){ //查询是否是同一个祖先
                cout<<"Y"<<endl;
            }else{
                cout<<"N"<<endl;
            }
        }
    }

}