【高阶数据结构】——并查集：高效地管理集合

前言：

并查集的原理

并查集（Disjoint-Set Data Structure）是一种用于管理集合的高效数据结构，特别适用于处理“动态连接”的问题，即动态地合并集合或查询两个元素是否属于同一个集合。并查集在计算机科学中有着广泛的应用，如用于解决最小生成树问题（Prim算法和Kruskal算法）、解决网络连通性问题、解决图论中的问题等。

并查集的基本操作

并查集主要支持以下三种基本操作：

实现方式

并查集有两种常见的实现方式：路径压缩和按秩合并。

C++实现

#include <iostream>
#include <vector>

class UnionFind {
private:
    std::vector<int> parent;
    std::vector<int> rank;

public:
    UnionFind(int n) : parent(n), rank(n) {
        for (int i = 0; i < n; ++i) {
            parent[i] = i;
            rank[i] = 1;
        }
    }

    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[rootY] = rootX;
        } else if (rank[rootX] < rank[rootY]) {
            parent[rootX] = rootY;
        } else {
            parent[rootY] = rootX;
            rank[rootX] += 1;
        }
    }

    bool connected(int x, int y) {
        return find(x) == find(y);
    }
};

int main() {
    int n, m;
    std::cin >> n >> m;
    UnionFind uf(n);
    for (int i = 0; i < m; ++i) {
        int a, b;
        std::cin >> a >> b;
        uf.unite(a - 1, b - 1); // 转换为0-based索引
    }
    for (int i = 0; i < m; ++i) {
        int a, b;
        std::cin >> a >> b;
        std::cout << (uf.connected(a - 1, b - 1) ? "YES" : "NO") << std::endl;
    }
    return 0;
}

C语言实现

#include <stdio.h>
#include <stdlib.h>

typedef struct {
    int parent[10001];
    int rank[10001];
} UnionFind;

void init(UnionFind *uf, int n) {
    for (int i = 0; i <= n; ++i) {
        uf->parent[i] = i;
        uf->rank[i] = 1;
    }
}

int find(UnionFind *uf, int x) {
    if (uf->parent[x] != x) {
        uf->parent[x] = find(uf, uf->parent[x]); // 路径压缩
    }
    return uf->parent[x];
}

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

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

int main() {
    int n, m;
    scanf("%d %d", &n, &m);
    UnionFind uf;
    init(&uf, n);
    for (int i = 0; i < m; ++i) {
        int a, b;
        scanf("%d %d", &a, &b);
        unite(&uf, a - 1, b - 1); // 转换为0-based索引
    }
    for (int i = 0; i < m; ++i) {
        int a, b;
        scanf("%d %d", &a, &b);
        if (find(&uf, a - 1) == find(&uf, b - 1)) {
            printf("YES\\n");
        } else {
            printf("NO\\n");
        }
    }
    return 0;
}