poj1988(并查集)-白红宇

poj1988(并查集)

阅读量：794 次

发布时间：2023-03-03

本文共 1323 字，大约阅读时间需要 4 分钟。

为了高效处理箱子合并和查询操作，我们采用并查集（Union-Find）结构。这个结构利用路径压缩和按秩合并，能够在合理时间内处理大量操作。

关键点总结：

初始化：

每个箱子初始时为独立一列，父节点指向自身，子树大小为1。

操作处理：

M x y：将箱子x所在的列合并到箱子y所在的列上。找到x和y的根节点，若不同，合并后更新父节点和子树大小。

C x：查询箱子x下方的箱子数量。通过并查集找到x的根节点，计算子树大小减去x到根的距离再减一。

并查集优化：

路径压缩：在查找操作中，压缩路径，使后续查询更快。

按秩合并：合并时根据子树大小决定主树，避免小树合并到大树，减少操作次数。

代码解析：

#include 
   
    #define MAXN 30001using namespace std;int pre[MAXN], son[MAXN], vis[MAXN];int find(int x) {    if (pre[x] == x) {        return x;    }    int temp = pre[x];    pre[x] = find(pre[x]);    vis[x] += vis[temp];    return pre[x];}void jion(int x, int y) {    int px = find(x);    int py = find(y);    if (px != py) {        pre[py] = px;        vis[py] = son[px];        son[px] += son[py];    }}int main() {    int p;    scanf("%d", &p);    for (int i = 1; i <= MAXN; ++i) {        pre[i] = i;        son[i] = 1;    }    for (int i = 1; i <= p; ++i) {        char s[2];        int x, y;        scanf("%s", s);        if (s[0] == 'M') {            scanf("%d%d", &x, &y);            jion(x, y);        } else {            scanf("%d", &x);            int root = find(x);            printf("%d\n", son[root] - vis[x] - 1);        }    }    return 0;}