并查集的本质-MuQYY的博客

一、并查集（Union-Find Set）的基本概念

1. 什么是并查集？

并查集是一种用于处理不相交集合（Disjoint Sets）合并及查询的问题的数据结构。
它支持两种操作：
- 查找（Find）：确定元素属于哪个集合。
- 合并（Union）：将两个不相交的集合合并成一个集合。

2. 并查集的用途

并查集常用于动态连通性问题，如判断两个元素是否在同一个集合中。
经典应用包括：
- 处理图中的连通分量。
- Kruskal 算法中用于检测是否会形成环。

二、并查集的实现

1. 基本结构

每个元素都有一个父节点指针 parent，初始时指向自身。
根节点是一个集合的代表元素，其父节点指向自身。

2. 基本操作

1）查找（Find）

目的：找到元素所属集合的根节点。
实现：递归或迭代地沿着父节点指针向上查找，直到找到父节点指向自身的节点。

int find(int x) {
    if (parent[x] != x)
        return find(parent[x]);
    else
        return x;
}

2）合并（Union）

目的：将两个不相交的集合合并成一个集合。
实现：将一个集合的根节点指向另一个集合的根节点。

void union_set(int x, int y) {
    int rootX = find(x);
    int rootY = find(y);
    if (rootX != rootY)
        parent[rootX] = rootY;
}

3. 优化技术

1）路径压缩（Path Compression）

在 find 操作中，将沿途的节点直接连接到根节点，加速后续的查找。

int find(int x) {
    if (parent[x] != x)
        parent[x] = find(parent[x]);
    return parent[x];
}

2）按秩合并（Union by Rank）

维护每个集合的高度（秩 rank），在合并时，总是将高度较小的树合并到高度较大的树上，减少树的高度。

void union_set(int x, int y) {
    int rootX = find(x);
    int rootY = find(y);
    if (rootX != rootY) {
        if (rank[rootX] < rank[rootY])
            parent[rootX] = rootY;
        else if (rank[rootX] > rank[rootY])
            parent[rootY] = rootX;
        else {
            parent[rootY] = rootX;
            rank[rootX]++;
        }
    }
}

三、带权并查集（Weighted Union-Find Set）

1. 什么是带权并查集？

带权并查集是在并查集的基础上，每个元素到其父节点（或根节点）之间附加一个权值，表示某种关系或差值。
通过维护这些权值，可以处理更复杂的关系，而不仅仅是判断连通性。

2. 应用场景

处理元素之间具有特定关系的并查集，如：
- 元素之间的距离、差值、比值。
- 食物链关系、代数方程中的等式和不等式关系。

四、带权并查集的实现原理

1. 权值的定义

weight[x]：表示元素 x 到其父节点的权值。
累积权值：元素到根节点的权值是从该元素到根节点路径上所有权值的累加（或根据具体问题可能是其他运算）。

2. 基本操作

1）查找（Find）

路径压缩时，更新每个节点到根节点的累积权值。

int find(int x) {
    if (parent[x] != x) {
        int temp = parent[x];
        parent[x] = find(parent[x]);
        weight[x] += weight[temp];  // 累加权值
    }
    return parent[x];
}

2）合并（Union）

在合并两个集合时，需要更新根节点的权值，以保持元素之间的关系一致。

void union_set(int x, int y, int w) {
    int rootX = find(x);
    int rootY = find(y);
    if (rootX != rootY) {
        parent[rootX] = rootY;
        weight[rootX] = weight[y] - weight[x] + w;  // 更新权值
    }
}

w 表示元素 x 和元素 y 之间的已知关系，如差值或比值。

3. 如何维护关系

目标：对于任意两个元素 x 和 y，希望维护它们之间的关系 relation(x, y)。
方法：在合并时，通过更新权值，确保元素之间的关系被正确维护。

五、例子：解决食物链问题

1. 问题描述

在一个动物王国中，有三类动物 A、B、C，它们的食物链关系是：

A 吃 B，B 吃 C，C 吃 A。

给定若干关于动物之间关系的陈述：

1 X Y：表示 X 和 Y 是同类。
2 X Y：表示 X 吃 Y。

需要判断哪些陈述是真实的，哪些是假的。

2. 如何建模

节点表示：每个动物是一个节点。
权值定义：对于两个动物 X 和 Y，定义它们之间的关系：
- 0：X 和 Y 是同类。
- 1：X 吃 Y。
- 2：Y 吃 X。
权值的运算规则：由于食物链是循环的，关系是模 3 的。

3. 带权并查集的应用

rank[x]：表示节点 x 到其父节点的关系。
累积权值：节点 x 到根节点的权值 rank[x]。

4. 代码实现

const int MAX_N = 50010;
int parent[MAX_N];  // 父节点
int rank[MAX_N];    // 权值

// 初始化
void init(int n) {
    for (int i = 1; i <= n; ++i) {
        parent[i] = i;
        rank[i] = 0;
    }
}

// 查找
int find(int x) {
    if (x != parent[x]) {
        int temp = parent[x];
        parent[x] = find(parent[x]);
        rank[x] = (rank[x] + rank[temp]) % 3;  // 更新权值，模 3
    }
    return parent[x];
}

// 合并
void union_set(int x, int y, int d) {
    int rootX = find(x);
    int rootY = find(y);
    if (rootX != rootY) {
        parent[rootX] = rootY;
        rank[rootX] = (rank[y] - rank[x] + d + 3) % 3;  // 更新权值
    } else {
        if ((rank[x] - rank[y] + 3) % 3 != d) {
            // 说明存在矛盾，陈述为假话
            ans++;
        }
    }
}

5. 示例

情景

陈述1：1 1 2，表示动物 1 和动物 2 是同类。
陈述2：2 2 3，表示动物 2 吃动物 3。
陈述3：2 3 1，表示动物 3 吃动物 1。

处理过程

陈述1：合并 1 和 2，关系为 0（同类）。
- parent[1] = 2，rank[1] = (rank[2] - rank[1] + 0 + 3) % 3 = 0。
陈述2：合并 2 和 3，关系为 1（2 吃 3）。
- parent[2] = 3，rank[2] = (rank[3] - rank[2] + 1 + 3) % 3 = 1。
陈述3：检查 3 和 1 的关系，要求 3 吃 1，即关系为 1。
- 通过 find，计算 rank[3] 和 rank[1]。
- 计算 (rank[3] - rank[1] + 3) % 3，如果不等于 1，则存在矛盾。