并查集回顾

acwing836—合并集合

#include<iostream>
#include<algorithm>
using namespace std;

const int N=1e5+10;
int n,m;
int p[N];

int find(int x)//找到x的祖宗节点
{
    if(x!=p[x])
        p[x]=find(p[x]);
    return p[x];
}

void merge(int x,int y)//把x的祖宗节点赋给y的祖宗节点的父节点。
{
    if(find(x)!=find(y))
        p[find(y)]=find(x);
    return ;
}


int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        p[i]=i;
    while(m--)
    {
        char a[3];
        cin>>a;
        int x,y;
        cin>>x>>y;
        //cout<<x<<y<<endl;
        if(a[0]==‘M‘)
        {
            merge(x,y);
        }
        else
        { 
            if(find(x)==find(y))
                cout<<"Yes"<<endl;
            else
                cout<<"No"<<endl;
            
        }
    }
}

并查集回顾

原文：https://www.cnblogs.com/forward-985/p/13685237.html