题目描述

合并集合

用树来存储集合，通过合并树来合并集合

通过查看几个节点的根节点是否相同来判断是否属于同一个集合

C++ 代码

#include<iostream>
using namespace std;
const int N=100010;
int q[N];                 //用来存放父亲结点
int n,m;
int find(int x)        //寻找x的父节点
{
    //如果x的父节点不是x，就继续往上找，找x的父节点的父节点因为根节点的父节点是他本身
    if(q[x]!=x)q[x]=find(q[x]);
    return q[x];      //最后返回x真正的父节点，即x所在集合的根节点
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)q[i]=i;       //父节点集合里存储从1到n的数字

    while(m--)
    {
        char op[2];
        int a,b;
        scanf("%s%d%d",op,&a,&b);

        if(op[0]=='M')
        {
            q[find(a)]=find(b); //将两个集合合并，即先找到a所在集合的根节点，他的父节点是b所在集合的父节点
        }
        else
        {
            if(find(a)==find(b))cout<<"Yes"<<endl;   //若a，b两个数字所在集合的根节点相同，则属于同一个集合
            else cout<<"No"<<endl;  //否则不是
        }
    }
    return 0;
}