本文共 2133 字，大约阅读时间需要 7 分钟。

并查集（Union-Find）是一种高效的数据结构，广泛用于解决并查集操作的时间复杂度问题。在这个问题中，我们需要实现并查集算法，并通过代码来展示其工作原理。

并查集的实现

并查集的核心思想是通过路径压缩和按秩合并两个操作来保持数据结构的高效性。路径压缩将节点直接指向根节点，减少查找时间；按秩合并则确保小树合并到大树中，保持树的平衡。

数据结构

初始化

• 创建父指针数组和计数器数组。
• 每个节点最初都是自己的父节点，计数器初始化为1。

查找操作

查找函数用于找到节点的根节点：

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

路径压缩技术确保查找操作的时间复杂度接近常数。

合并操作

合并函数用于将两个节点合并到同一集合中：

void joint(int x, int y) {
    if (find(x) == find(y)) return;
    if (cnt[find(x)] > cnt[find(y)]) {
        par[find(y)] = find(x);
        cnt[find(x)] += cnt[find(y)];
    } else {
        par[find(x)] = find(y);
        cnt[find(y)] += cnt[find(x)];
    }
}

按秩合并确保小树合并到大树中，保持树的高度较低。

代码实现

#include 
   
    
#include 
    
     
using namespace std;
const int MAX_N = 2e5 + 5;
int par[MAX_N], cnt[MAX_N];
unordered_map
     
       umap;
void init(int n) {
    for (int i = 0; i < n; ++i) {
        par[i] = i;
        cnt[i] = 1;
    }
}
int find(int x) {
    if (par[x] == x) return x;
    return par[x] = find(par[x]);
}
void joint(int x, int y) {
    if (find(x) == find(y)) return;
    if (cnt[find(x)] > cnt[find(y)]) {
        par[find(y)] = find(x);
        cnt[find(x)] += cnt[find(y)];
    } else {
        par[find(x)] = find(y);
        cnt[find(y)] += cnt[find(x)];
    }
}
int main() {
    int T;
    cin >> T;
    while (T--) {
        int n;
        cin >> n;
        int cntv = 0;
        for (int i = 0; i < n; ++i) {
            int x, y;
            cin >> x >> y;
            if (umap.find(x) == umap.end()) {
                ++cntv;
                umap[x] = cntv;
            }
            if (umap.find(y) == umap.end()) {
                ++cntv;
                umap[y] = cntv;
            }
            joint(umap[x], umap[y]);
        }
        int result = 0;
        for (int i = 0; i <= cntv; ++i) {
            result = max(result, cnt[find(i)]);
        }
        cout << result << endl;
    }
    return 0;
}
     
    
   

代码解释

通过上述代码，我们可以高效地实现并查集算法，解决并查集操作的时间复杂度问题。

转载地址：http://hsbiz.baihongyu.com/