题解 P3367 【模板】并查集

#include<iostream>
#include<cstdio>
using namespace std;
int n,m,x,y,z;
int f[150000]; //f[i]表示i的祖先 
inline int find(int x){ //inline是把这个函数插入到调用的地方，速度会快一点 
    if(f[x]==x) return f[x]; //如果找到了根就返回 
    return f[x]=find(f[x]); //没有找到就一直递归，直到找到，找到的同时压缩路径 
}
inline void join(int a,int b){ //把a、b加入并查集 
    int fa=find(f[a]),fb=find(f[b]); //分别找到a、b的祖先 
    f[fa]=fb; //把a、b的祖先连起来 
}
int main(){
    int i,j;
    scanf("%d%d",&n,&m);
    for(i=1;i<=n;i++) f[i]=i; //对每一个f赋初值 
    for(i=1;i<=m;i++){
        scanf("%d%d%d",&z,&x,&y);
        if(z==1) join(x,y);
        else if(find(f[x])==find(f[y])) printf("Y\n");
         else printf("N\n");
    }
}