如何理解find函数

1. 如果 x != p[x] 说明父节点不是自己，这时还不知道祖先节点是谁，所以递归查找find(p[x])
2. 如果 x == p[x] 说明找到祖先节点，返回结果p[x]. （似乎x==p[x],为什么返回p[x]呢？）因为回溯更新的是p[x],p[x]才存着祖先节点
3. p[x] = find(p[x]) 同时完成路径压缩
4. 时间复杂度近乎是O(1)

看见大佬的find函数，回来更新一下

int find(int x) {
    return x == p[x] ? x : p[x] = find(p[x]);
}

这里为什么可以返回x呢，因为祖先节点的父节点就是他自己，其他层返回的都是p[x]

C++ 代码

#include <bits/stdc++.h>

using namespace std;

const int N = 100010;

int p[N];

int find(int x) { //找祖先节点+路径压缩 
    if (p[x] != x) p[x] = find(p[x]);
    return p[x];
}

int main() {
    int n, m;
    scanf("%d%d", &n, &m);

    for (int i = 0; i < n; i++) p[i] = i; 
    while (m --) {
        char s[2];
        int a, b;
        scanf("%s%d%d", s, &a, &b);

        if (s[0] == 'M') p[find(a)] = find(b);
        else {
            if (find(a) == find(b)) puts("Yes");
            else puts("No");
        }
    }
    return 0;
}