ac 836合并集合

并查集:

1. 将两个集合合并
2. 询问两个元素是否在同一个集合里

基本原理: 每个集合用一棵树来表示，树根的编号就是整个集合的编号，每个节点储存他的父节点，p[x]表示x的父节点

1. 判断父节点 if(p[x] == x)
2. 如何求x的集合编号： while(p[x] != x) x = p[x]
3. 如何合并两个集合： px是x集合编号py是y的集合编号 p[x] = y （即两个树随便其中一个根节点指向另一个根节点）

主要是一个find函数，这个函数的作用就是返回参数x的祖宗节点， 如果p[x]不是祖宗节点，就让p[x]等于祖宗节点（递归) 最后返回他的祖宗节点
如果合并就让两个树随便其中一个根节点指向另一个根节点

#include<bits/stdc++.h>
using namespace std;

const int N = 100010;
int p[N];

int find(int x){
    //返回x所在集合的编号（即根节点,祖宗节点)
    if (p[x] != x) p[x] = find(p[x]);
    return p[x];
}
int main() {
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        p[i] = i;
    }
    for (int i = 0; i < m; i ++) {
        char c;
        int x, y;
        cin >> c >> x >> y;
        if (c == 'M') {
             p[find(x)] = find(y);
        }
        else if (c == 'Q') {
            if (find(x) == find(y)) puts("Yes");
            else puts("No");
        }
    }
}