python/TangDou/AcWing/DisjointSet/POJ1988.cpp

#include <iostream>
#include <cstdio>

using namespace std;
const int N = 30010;
int T;     // 操作数量
int p[N];  // 并查集数组
int sz[N]; // 每个家族中节点数量
int d[N];  // 每个节点到根节点的距离
char op;   // 操作符

// 带权并查集模板
int find(int x) {
    // 点权的理解：每个点到根的距离
    if (p[x] == x) return x; // 自己是老大，返回自己
    int px = find(p[x]);     // 通过自己父亲找老大
    d[x] += d[p[x]];         // 点权在路径压缩过程中，需要加上父亲的点权
    return p[x] = px;        // 路径压缩
}

// 合并并查集
void join(int x, int y) {
    int px = find(x), py = find(y);
    if (px != py) {
        p[py] = px; // px所在的子树放到py所在子树之上
        // 下面这句话是本题相关的修改，重要！！！
        d[py] = sz[px];   // py到px的距离就是px所在子树的结点个数[这个转换太漂亮了]
        sz[px] += sz[py]; // px所在子树结点个数要加上py这一棵树子树
    }
}

int main() {
    // p父结点 sz当前节点子树大小 dis当前节点到根结点距离
    for (int i = 1; i <= N - 10; i++) p[i] = i, sz[i] = 1;
    cin >> T;
    while (T--) {
        cin >> op;
        int x, y;
        if (op == 'M') { // 合并
            cin >> x >> y;
            join(x, y);
        } else {
            cin >> x;
            // 查找某一个点x下边有几个点时，只用求出x根结点所在子树的结点个数-x到根结点的距离-1
            printf("%d\n", sz[find(x)] - d[x] - 1);
        }
    }
    return 0;
}