2023.11.21做题笔记（并查集）

#include<iostream>
using namespace std;

const int N=100005;
int a[N];

int find(int x)
{
    if(x==a[x])return x;
    a[x]=find(a[x]);
    return a[x];
}

void hebing(int x,int y)
{
    if(find(x)!=find(y))
    {
        a[find(x)]=find(y);
    }
}

void check(int x,int y)
{
    if(find(x)==find(y))cout<<"Y"<<endl;
    else cout<<"N"<<endl;
}

int main()
{
    for(int i=0;i<N;i++)a[i]=i;
    int n,m;
    cin>>n>>m;
    int x,y,z;
    for(int i=0;i<m;i++)
    {
        cin>>z>>x>>y;
        if(z==1)hebing(x,y);
        else if(z==2)check(x,y);
    }
    system("pause");
    return 0;
}

    #include<bits/stdc++.h>//并查集 
    using namespace std;
    int a1,a2,a3,f[200001],n,m;
    int getf(int o) {//不停找爹，直到找到祖宗为止 
        if (f[o]==o) return o;
        else return f[o]=getf(f[o]);//这里是路径压缩，把递归过程中遇到的
                                    //结点的祖宗结点也直接修改了。
    }
    void merge(int v,int u) {//合并子集 
        int t1,t2;//t1,t2分别为v和u的祖宗
        t1=getf(v);//获取祖宗结点值
        t2=getf(u);
        if (t1!=t2) f[t2]=t1;//靠左。即将右边的集合，作为左边的子集
        return; 
    }
    void find(int v,int u) {
        int t1,t2;//同上
        t1=getf(v);
        t2=getf(u);
        if (t1==t2) printf("Y\n");
        else printf("N\n");
    }
    int main(){
        scanf("%d %d",&n,&m);
        for (int i=1;i<=n;i++) f[i]=i;//初始化集合
        for (int i=1;i<=m;i++) {
            scanf("%d %d %d",&a1,&a2,&a3);
            if (a1==1) merge(a2,a3);
            else find(a2,a3);
        }
    }