并查集

思想：

• find操作：采用压缩路径方法，让每个人都递归找自己的父节点，直到某人父节点就是他自己本身，则他就是根节点。然后在递归反哺回去，让每个节点的父节点直接等于根节点，这会给下次进行find操作节省时间，不用在递归那么深。

• find压缩路径几何思想，想像一阶树，有n个节点，n层高。然后通过压缩路径，递归后将他们的父节点全部改为根节点。变成n-1阶树，两层高。

• 优化后的合并操作：由于merge操作本质是为后续find操作进行服务，树越高，find递归遍历到根节点的时间就更长。如果无脑合并，树就会不受限制的疯长，导致查询效率变低。所以优化思想就是：

  1. 将矮树根节点并到高树根节点，这样就不会使合并后的高树长得更高。
  2. 如果两棵树一样高，则让合并后那个棵树高度+1；

时间复杂度

• 路径压缩优化后的并查集 ： O(logn)
• 路径压缩 + merge优化 = O(logn) - O(1) , 无限接近O(1)

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

const int N = 100010;
int p[N],r[N];
int n,m;

int find(int x){                 // 采用压缩路径思想，让每个子节点直接指向根节点。
    if(p[x] != x) p[x] = find(p[x]);   // 递归思想，从最后一层得到根节点，反馈回去，使每个节点的父节点都等于根节点。
    return p[x];
}


void merge(int a,int b){         。
    a = find(a) , b = find(b);   // 找到各自的根节点。
    if( r[a] > r[b] ) p[b] = a;  // 如果b树的大小比a树小，则将b树并到a树
    else{
        p[a] = b;
        if(r[a] = r[b]) r[b]++;  // 由于a已经并到b,如果高度相同，则b树高度加一
    }
}


int main(){
    cin >> n >> m;
    for(int i = 0; i < N ; i++){
        p[i] = i;
        r[i] = 1;// 其实这行可以省略，因为全局变量默认为0也有同样效果。
    }
    while(m--)
    {
        string mode;
        int a, b;
        cin >> mode >> a >> b;

        if(mode == "M")
            merge(a,b);
        if(mode == "Q"){
            if(find(a)==find(b)) cout << "Yes" <<endl;
            else cout << "No" << endl;
        }
    }
    return 0;
}