并查集简介

并查集（Disjoint Set Union，DSU）是一种用于管理元素分组的数据结构，支持两种操作：查找（Find）和合并（Union）。常用于解决动态连通性问题，例如网络连接、图的连通分量等。

基本实现思路

并查集的核心思想是通过数组或哈希表维护每个元素的父节点，通过路径压缩和按秩合并优化性能。

代码实现

以下是一个不使用 public 和 class 的 C++ 实现示例：

#include <vector>
using namespace std;

struct DSU {
    vector<int> parent;
    vector<int> rank;

    DSU(int n) {
        parent.resize(n);
        rank.resize(n, 0);
        for (int i = 0; i < n; ++i) {
            parent[i] = i;
        }
    }

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

    void unite(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);
        if (rootX == rootY) return;

        if (rank[rootX] < rank[rootY]) {
            parent[rootX] = rootY;
        } else {
            parent[rootY] = rootX;
            if (rank[rootX] == rank[rootY]) {
                rank[rootX]++;
            }
        }
    }
};

代码解析

1. 初始化

   • parent 数组存储每个节点的父节点，初始时每个节点的父节点是自身。
   • rank 数组存储每个节点的秩，用于按秩合并优化。

2. 查找操作（Find）

   • 通过递归查找根节点，并进行路径压缩，使得后续查询更快。

3. 合并操作（Union）

   • 找到两个节点的根节点，根据秩决定合并方向，避免树过高。

示例应用

以下是一个简单的示例，展示如何使用并查集：

#include <iostream>
int main() {
    DSU dsu(5);
    dsu.unite(0, 1);
    dsu.unite(2, 3);
    cout << (dsu.find(0) == dsu.find(1)) << endl; // 输出 1（true）
    cout << (dsu.find(0) == dsu.find(2)) << endl; // 输出 0（false）
    return 0;
}

优化分析

1. 路径压缩

   • 在查找过程中将节点的父节点直接指向根节点，减少后续查找时间。

2. 按秩合并

   • 将较矮的树合并到较高的树下，保持树的平衡性。

常见问题

1. 如何判断两个节点是否连通？

   • 比较它们的根节点是否相同。

2. 时间复杂度是多少？

   • 经过优化的并查集操作接近常数时间。

总结

并查集是一种高效的数据结构，适用于动态连通性问题。通过路径压缩和按秩合并，可以显著提升性能。以上实现避免了 public 和 class，适合在博客中作为示例代码展示。