并查集—合并集合

并查集可以表示元素中的属于状态，比较重要。其核心元素是father数组，初始化如下：

void init() {
		for(int i = 0; i < n; i++) {
			father[i] = i
		}
}

另外就是查找元素x的父亲：

//普通版
int find(int x) {
		while(x != father[x]){
			x = father[x];
		}
}
//路径压缩优化（推荐）
int find(int x) {
		return x == father[x] ? x : find(father[x]);
}

合并集合：

//普通版
void merge(int a, int b) {
		a = find(a), b = find(b);
		if(find(a) != find(b)) father[b] = a;
}

//启发式合并，即将矮树合并到高树
void merge(int a, int b) {
		a = find(a), b = find(b);
		//如果a的父亲的高度小于b的父亲的高度
		if(rank[a] <= rank[b]) father[a] = b;
		else father[b] = a;
		//如果两树的高度是不同的，且a和b的父亲不相同，那就要更新高度。否则整体树的高度是不变的（画图可以看出）
		if(rank[a] != rank[b] && a != b) rank[b]++;
}

Acwing

#include <iostream>
using namespace std;
const int MAXN = 100010;
char mode;
int a, b, n, t;
//  并查集，树的高度数组（rank数组）
int father[MAXN], rk[MAXN];

void init() {
    //  高度初始化为1
    for(int i = 0; i < n; i++) father[i] = i, rk[i] = 1;
}

//  递归法可以压缩路径
int find(int x) {
    return x == father[x] ? x : find(father[x]);
}

//  启发式合并 = 按树的高度合并
void merge(int a, int b) {
    //  找爹
    int fathera = find(a), fatherb = find(b);
    //  如果a的爹的高度小于等于b的爹的高度（把a的爹合并到b的爹）即将矮的树合并到高的树
    if (rk[fathera] <= rk[fatherb]) father[fathera] = fatherb;
    else father[fatherb] = fathera;
    //  只有在两个树的高度相同的时候，才会更新树的高度。不然高度是不变的。
    if (rk[fathera] == rk[fatherb] && fathera != fatherb) rk[fatherb] ++;
}

int main() {
    cin >> n >> t;
    init();
    while(t--) {
        cin >> mode >> a >> b;
        if(mode == 'M') {
            merge(a, b);
        } else {
            if(find(a) == find(b)) cout <<"Yes\n";
            else cout << "No\n";
        }
    }
}