c++中如何实现并查集的查找_c++并查集查找方法

并查集通过父节点数组实现，初始化时每个节点指向自己，find函数递归查找根节点并进行路径压缩，降低树高以提升效率，配合按秩合并可接近O(1)操作。

在C++中实现并查集（Disjoint Set Union, DSU）的查找操作，核心是通过数组记录每个节点的父节点，并使用路径压缩优化查找效率。

基本结构定义

并查集通常用一个vector或数组来维护每个元素的父节点。初始化时，每个元素的父节点指向自己，表示各自为独立集合。

#include 
using namespace std;

vector parent;

// 初始化：每个节点的父节点是自己
void init(int n) {
    parent.resize(n);
    for (int i = 0; i < n; ++i) {
        parent[i] = i;
    }
}

查找函数实现

find 函数用于查找某个元素所在集合的根节点（代表元）。通过递归方式向上查找，并在回溯时将沿途节点直接挂到根节点下，实现路径压缩。

int find(int x) {
    if (parent[x] != x) {
        parent[x] = find(parent[x]); // 路径压缩
    }
    return parent[x];
}

路径压缩的作用是降低树的高度，使后续查找接近 O(1) 时间复杂度。

万兴喵影

国产剪辑神器

下载

立即学习“C++免费学习笔记（深入）”；

按秩合并优化（可选）

为了进一步提升性能，可以引入秩（rank）数组，在合并时将低秩树接到高秩树上，避免退化成链。

vector rank;

void unite(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]++;
        }
    }
}

使用示例

完整的小例子演示如何初始化、查找和合并：

#include 
#include 
using namespace std;

vector parent, rank;

void init(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 rx = find(x), ry = find(y);
    if (rx == ry) return;
    if (rank[rx] < rank[ry]) parent[rx] = ry;
    else if (rank[rx] > rank[ry]) parent[ry] = rx;
    else {
        parent[ry] = rx;
        rank[rx]++;
    }
}

int main() {
    init(5);
    unite(0, 1);
    unite(1, 2);
    cout << "Find(0): " << find(0) << endl; // 输出根节点
    cout << "Find(2): " << find(2) << endl; // 应与find(0)相同
    return 0;
}