imicola's Blog

并查集

5分钟阅读

图 模板
并查集维护的是多个不相交的集合，支持两种操作:

  • 查找:查找某个元素所属的集合
  • 合并:将两个元素合并成一个

用于维护并查集数据结构是多颗 树 组成的 森林

原理

查询

  • 在使用并查集时候，设立一个数组 parent 来记录每个元素的父节点：
    • 如果 parent[i] = i ,表明 是自己的根，即它是一个独立的集合
    • 如果 parent[i] = j,说明 属于 这个集合
    • 当我们想查询 时候,我们可以递归查询 parent[i]
      合并
  • 我们若要实现对两个数组 parent_i 和 parent_j 的合并
    • 我们只需要将一棵树的根指向另一颗树即可
    • 换句话说，我们只需要将 parent[i] = j即可

基础实现

const int N = 1e7;
vector<int> parent(N);
 
void init()
{
    for (size_t i = 0; i < N; i++) {
        parent[i] = i;
    }
}
 
int dsufind(int x)
{
    if (parent[x] == x) return x;
    return dsufind(parent[x]);
}
 
void union_set(int x, int y)
{
    int rootx = x;
    int rooty = y;
    if (rootx != rooty) parent[x] = y;
}
 
void solve()
{
    init();
    union_set(1, 2);
    union_set(3, 1);
    cout << dsufind(3);
}

并查集的优化

  • 在对并查集的基本实现中,查找可能会遍历很深的树,为了提高效率,我们引入路径压缩和按秩合并

路径压缩

在dsufind过程中，让x直接指向根，减少查找的层数

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

按秩合并

目标： 在 union_set(x, y) 时，让“矮的树”挂到“高的树”下面，减少树的高度

方法： 维护一个 rank[] 数组，表示树的高度：

  • rank[rootX] > rank[rootY]：让 rootY 挂到 rootX 下
  • rank[rootX] < rank[rootY]：让 rootX 挂到 rootY 下
  • rank[rootX] == rank[rootY]：任选一个为根，并 rank++
void union_set(int x, int y)
{
    int rootx = x;
    int rooty = y;
    if (rootx != rooty) {
        if (ranks[rootx] > ranks[rooty]) {
            parent[rooty] = rootx;
        }
        else if (ranks[rootx] < ranks[rooty]) {
            parent[rootx] = rooty;
        }
        else {
            parent[rootx] = rooty;
            ranks[rootx]++;
        }
    }
}

在优化后的并查集时间复杂度为 其中为阿克曼函数的逆，增长极慢，可以近似表现为

unordered_map作为数据结构的并查集

当我们试图对字符串做并查集操作的时候，我们可以利用到unordered_map<string,string>作为数据结构基础来实现并查集

我们这里用类给出

class dsuFind {
private:
    unordered_map<string, string> parent;  // 存储每个字符串的父节点
    unordered_map<string, int> rank;       // 按秩合并，记录树的高度
 
public:
    // 查找（带路径压缩）
    string find(string x) {
        if (parent.find(x) == parent.end()) parent[x] = x;  // 如果 x 不在并查集，初始化
        if (parent[x] != x) parent[x] = find(parent[x]);  // 路径压缩
        return parent[x];
    }
    // 合并（按秩合并）
    void union_set(string x, string y) {
        string rootX = find(x);
        string rootY = find(y);
        if (rootX != rootY) {
            if (rank[rootX] > rank[rootY]) {
                parent[rootY] = rootX;
            } else if (rank[rootX] < rank[rootY]) {
                parent[rootX] = rootY;
            } else {
                parent[rootX] = rootY;
                rank[rootY]++;
            }
        }
    }
    // 判断两个字符串是否在同一集合
    bool isConnected(string x, string y) {
        return find(x) == find(y);
    }
};

当然对整数我们也可以使用unordered_map来构造树，但是在大部分情况下都没有数组效率高

特别的，当n特别大且是离散的时候我们可以使用unordered来作为树的结构

关系图谱