并查集 · Zwing's blog

并查集 ADT 核心定义

并查集（Disjoint Sets/Union-Find）是一种维护不相交动态集合的数据结构，集合族记为 \(S=\{S_1,S_2,...,S_k\}\)，每个集合有一个代表元（leader）

支持三大核心操作：

MakeSet(x)：创建仅包含元素 \(x\) 的集合，并将其加入集合族 \(S\)
Find(x)：返回 \(x\) 所属集合的代表元指针
Union(x,y)：找到 \(x\) 所属集合 \(S_x\) 和 \(y\) 所属集合 \(S_y\)，移除两者并加入其并集

典型应用：计算图的连通分量

链表实现

// 1. 链表元素节点（链表存储集合元素，每个元素指向所属集合）
struct SetNode {
    int value;               // 元素值
    SetNode* next;           // 链表下一个节点指针
    class DisjointSet* set;  // 指向所属的集合对象（用于快速Find）
    explicit SetNode(int val) : value(val), next(nullptr), set(nullptr) {}
};

// 2. 并查集集合对象（集合对象含链表头尾指针，维护集合大小）
class DisjointSet {
public:
    SetNode* head;  // 链表头指针（代表元，链表第一个元素）
    SetNode* tail;  // 链表尾指针（用于快速追加）
    int size;       // 集合大小（用于加权合并）

    explicit DisjointSet(SetNode* node) : head(node), tail(node), size(1) {
        node->set = this;  // 元素关联到当前集合
    }
};

// 3. 链表实现的并查集管理类
class UnionFindLinkedList {
    unordered_map<int, SetNode*> valToNode;  // 值到节点的映射，用于快速查找节点

public:
    // MakeSet(x)——创建仅含 x 的集合，加入集合族
    void MakeSet(int x) {
        // 避免重复创建
        if (valToNode.find(x) != valToNode.end()) return;
        // 1. 创建元素节点
        SetNode* newNode = new SetNode(x);
        // 2. 创建集合对象（包含该节点）
        DisjointSet* newSet = new DisjointSet(newNode);
        // 3. 记录值到节点的映射
        valToNode[x] = newNode;
    }

    // Find(x)——返回 x 所属集合的代表元（链表头）
    int Find(int x) {
        // 检查 x 是否存在
        if (valToNode.find(x) == valToNode.end()) {
            return -1;
        }
        // 通过节点的 set 指针直接找到集合，返回表头（代表元）
        SetNode* node = valToNode[x];
        int leader = node->set->head->value;
        return leader;
    }

    // Union(x,y)（按大小合并）
    void UnionWeighted(int x, int y) {
        // 1. 查找 x 和 y 所属集合
        SetNode* xNode = valToNode[x];
        SetNode* yNode = valToNode[y];
        if (!xNode || !yNode) {
            return;
        }
        DisjointSet* setX = xNode->set;
        DisjointSet* setY = yNode->set;
        if (setX == setY) {
            return;
        }

        // 2. 确保 setX 是更大的集合（小集合追加到大链表，减少指针更新次数）
        if (setX->size < setY->size) {
            swap(setX, setY);  // 交换后setX始终更大
        }

        // 3. 合并操作
        setX->tail->next = setY->head;
        setX->tail = setY->tail;
        setX->size += setY->size;

        // 4. 更新小集合 setY 的所有元素指针
        SetNode* curr = setY->head;
        while (curr) {
            curr->set = setX;
            curr = curr->next;
        }

        // delete setY; // 5. 释放setY
    }
}

复杂度分析：

MakeSet(x)：\(O(1)\)
Find(x)：\(O(1)\)
Union(x,y)：\(O(lgn)\)

考虑如下伪代码

MakeSet(x0)
for i := 1 to n
  MakeSet(xi)
  Union(xi, x0)

如果不使用加权合并，时间复杂度为 \(O(n^2)\)，单次平均时间复杂度为 \(O(n)\)

使用加权合并后，时间复杂度优化为 \(O(n)\)，单次平均时间复杂度为 \(O(1)\)

平均为 \(O(logn)\)，关键证明：每个元素的集合指针最多更新 \(O(logn)\)次，因每次更新后所在集合大小至少翻倍

有根树实现

注意，这里的树不是二叉树

class UnionFindTreeBasic {
    unordered_map<int, int> parent;  // 节点到父节点的映射（每个节点有父指针）
public:
    // MakeSet(x)——创建仅含x的树，x的父是自身（根节点）
    void MakeSet(int x) {
        if (parent.contains(x)) return;
        parent[x] = x;  // 根节点的父是自己
    }

    // Find(x)——迭代找根（避免递归栈溢出）
    int Find(int x) {
        if (!parent.contains(x)) {
            return -1;
        }
        // 从x向上遍历，直到父节点等于自身（根）
        int curr = x;
        while (parent[curr] != curr) {
            curr = parent[curr];
        }
        return curr;
    }

    // Union(x,y)——将x的根挂到y的根下（无优化）
    void Union(int x, int y) {
        int rootX = Find(x);
        int rootY = Find(y);
        if (rootX == -1 || rootY == -1 || rootX == rootY) {
            return;
        }
        // 将rootX的父设为rootY（简单合并，可能形成链）
        parent[rootX] = rootY;
    }
};

考虑到这种情况下树有可能退化为链表，故有以下两种避免成链表的第一层优化：

按大小合并
按高度合并

优化 1：按大小合并

class UnionFindTreeBySize {
    unordered_map<int, int> parent;  // 节点到父节点
    unordered_map<int, int> size;    // 根节点到树的大小（按大小合并需维护树大小）

public:
    void MakeSet(int x) {
        if (parent.contains(x)) return;
        parent[x] = x;  // 根节点
        size[x] = 1;    // 初始树大小为1
    }
    
    int Find(int x) {
        // 同上
    }

    // 按大小合并——小棵树挂到大连树根下，减少树深
    void Union(int x, int y) {
        int rootX = Find(x);
        int rootY = Find(y);
        if (rootX == -1 || rootY == -1 || rootX == rootY) {
            return;
        }
        // 小棵树挂到大连树根下
        if (size[rootX] < size[rootY]) {
            parent[rootX] = rootY;  // rootX 挂到 rootY 下
            size[rootY] += size[rootX];  // 更新 rootY 的树大小
        } else {
            parent[rootY] = rootX;  // rootY 挂到 rootX 下
            size[rootX] += size[rootY];
        }
    }
};

优化 2：按高度合并

class UnionFindTreeByHeight {
    unordered_map<int, int> parent;  // 节点到父节点
    unordered_map<int, int> height;  // 根节点到树的高度

public:
    void MakeSet(int x) {
        if (parent.contains(x)) return;
        parent[x] = x;    // 根节点
        height[x] = 0;    // 初始树高为 0（单节点树）
    }
    
    int Find(int x) {
        // 同上
    }

    // 按高度合并——矮树挂到高树根下，高度相同才更新高度
    void Union(int x, int y) {
        int rootX = Find(x);
        int rootY = Find(y);
        if (rootX == -1 || rootY == -1 || rootX == rootY) {
            return;
        }
        // 矮树挂到高树根下
        if (height[rootX] < height[rootY]) {
            parent[rootX] = rootY;  // rootX 挂到 rootY 下，rootY 高度不变
        } else {
            parent[rootY] = rootX;  // rootY 挂到 rootX 下
            // 若高度相同，合并后 rootX 高度 +1
            if (height[rootX] == height[rootY]) {
                height[rootX]++;
            }
        }
    }
};

这两种优化方式均将 Find 和 Union 的最坏情况时间复杂度优化至 \(O(logn)\)

那么还有无更好的优化方式？

Union 更改父节点的操作非常快，瓶颈还是在于 Find，若能进一步加速 Find 操作将可以得到更好的性能

路径压缩 + 按秩合并

class UnionFindTreeFinal {
    unordered_map<int, int> parent;  // 节点到父节点
    unordered_map<int, int> rank;    // 节点到秩（秩是高度的上界，路径压缩后无需维护真实高度）

public:
    // MakeSet(x)——根节点父为自身，秩初始化为 0
    void MakeSet(int x) {
        if (parent.contains(x)) return;
        parent[x] = x;
        rank[x] = 0;
    }

    // Find(x)——带路径压缩（扁平化树结构）
    // 原来 1→2→3→4
    // 压缩后 1→4、2→4、3→4
    // 下一次查找就一步到位
    int Find(int x) {
        if (!parent.contains(x)) {
            return -1;
        }
        // 递归实现路径压缩：找到根后，将当前节点的父直接设为根
        if (parent[x] != x) {
            parent[x] = Find(parent[x]);  // 核心：父节点指向根，扁平化树
        }
        return parent[x];
    }

    // Union(x,y)——按秩合并（低秩树挂到高秩树根下）
    void Union(int x, int y) {
        int rootX = Find(x);
        int rootY = Find(y);
        if (rootX == -1 || rootY == -1 || rootX == rootY) {
            return;
        }
        // 按秩合并：低秩挂到高秩下
        if (rank[rootX] < rank[rootY]) {
            parent[rootX] = rootY;  // rootX挂到rootY下，rootY秩不变
        } else {
            parent[rootY] = rootX;  // rootY挂到rootX下
            // 若秩相等，合并后rootX秩+1
            if (rank[rootX] == rank[rootY]) {
                rank[rootX]++;
            }
        }
    }
};

使用路径压缩后，发现树高属性不在适用，故引出 “秩” 属性

秩是高度的上界，路径压缩后无需维护真实高度

哈希表与数组

unordered_map<int, int> parent;
unordered_map<int, int> rank;

哈希表灵活性非常大，尤其是 Find 操作对无法找到的特判，但这也拖累了性能

如果对于预先知道操作对象而不需要特判的情况，可以采用 vector 实现，性能会得到大幅提升

class DisjointSets
{
    vector<int> parent;
    vector<int> rank;
public:
    explicit DisjointSets(int n) // 构造函数，初始化容量
    {
        parent.resize(n);
        rank.assign(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 Union(int x, int y)
    {
        int xRoot = Find(x);
        int yRoot = Find(y);

        if (xRoot == yRoot)
        {
            return;
        }
        if (rank[xRoot] > rank[yRoot])
        {
            parent[yRoot] = xRoot;
        }
        else
        {
            parent[xRoot] = yRoot;
            if (rank[xRoot] == rank[yRoot])
            {
                rank[yRoot]++;
            }
        }
    }
};

哈希表 VS 动态数组：

优先选 vector 的场景：
- 节点是非负整数，且范围已知、连续（如 0~n-1）
- 追求极致性能（如大规模数据、频繁 Find/Union）
- 节点密度高（几乎所有编号都被使用）
优先选 unordered_map 的场景：
- 节点是稀疏分布（如随机 ID、零散整数）或范围未知
- 节点编号可能是负数、字符串等非连续非负整数
- 无需预先确定节点总数，动态添加场景多