并查集

简介

并查集是用来快速查询两个元素是否在同一个集合的数据结构。并查集有两个基本操作：集合合并，查询元素所在的集合。
时间复杂度的难点在于集合的合并，如果是线性数据结构的话，合并集合的复杂度至少要O(N)。
因此可以通过树形结构，集合的合并可以通过加一条边的方式，这样的话，合并的复杂度是O(1)。那么通过树形结构的查询操作是怎样的呢？查询操作可以通过查找树形结构根节点的序号代表集合的序号，如果两个树形结构的根节点是同一个，那么就直接判断出来了。
另外衍生出来的问题就是，查询操作的时间复杂度是树的高度，我们当然希望树的高度是1，因此如果再查询操作碰到树的高度超过1的，就把该路径所有的父节点指向最终的根节点。这种优化称为路径压缩。

代码

#include <iostream>
using namespace std;
#define N 100010
// 并查集查找 + 路径压缩
int find(int *p, int x) {
    if(p[x] != x) {
        p[x] = find(p, p[x]);
    }
    return p[x];
}
int main() {
    int n, m;
    while(scanf("%d %d", &n, &m) != EOF) {
        int p[N];
        char c;
        int x, y;
        for (int i = 0; i < n; i ++) {
            p[i] = i;
        }
        for (int i = 0; i < m; i ++) {
            cin >> c;
            scanf("%d %d", &x, &y);
            // 合并操作
            if(c == 'M') {
                p[find(p, x)] = find(p, y);
            } else {
                // 查询操作
                if(find(p, x) == find(p, y)) {
                    cout << "Yes" << endl;
                } else {
                    cout << "No" << endl;
                }
            }
        }
    }
    return 0;
}