并查集

有编号从0~n-1的数字数列，以数的形式储存数列，初始时每个数列只有一个头结点，下面实现两个功能，将编号为a,b的数列合并为一个数列，或查询编号为a，b的数字是否在一个数列

代码如下（核心：找到祖宗节点，并实现路径压缩）

#include<iostream>
using namespace std;
const int N=100010;
int p[N];
int n,m;
int find(int x){
    if(p[x]!=x) p[x]=find(p[x]);
    return p[x];
}//找到并返回祖宗节点，并压缩路径,if成立条件是x节点不是树根，并且，找到祖父节点即find(p[x]),并将p[x]更新成祖父节点
int main(){
    scanf("%d%d",&n,&m);
    for(int i=0;i<n;i++) p[i]=i;
    while(m--){
        char op[2];
        int a,b;
        scanf("%s%d%d",op,&a,&b);
        if(op[0]=='M'){
            p[find(a)]=find(b);//将一个头节点设置在另一个节点后面，这样两个数列就实现了合并
        }
        else{
            if(find(a)==find(b)) printf("Yes\n");//判断两个数字的头节点是否相同//
            else printf("No\n");
        }
    }
    return 0;
}