当前没有测试数据。

一、概念定义

并查集（Union-Find）是一种用于管理不相交集合的数据结构，支持合并（Union）和查询（Find）两种操作：

• 合并：将两个集合合并为一个。
• 查询：判断两个元素是否属于同一集合。

二、核心要点

1. 数组存储：用数组 parent 记录每个元素的父节点，初始时 parent[x] = x。
2. 路径压缩：在查询时将节点直接连接到根节点，优化后续查询效率。
3. 按秩合并（可选优化）：合并时将小树合并到大树，避免树高度过快增长。
4. 时间复杂度：路径压缩+按秩合并后，单次操作接近 O(1)。

三、经典示例

1. 基础实现（含路径压缩）

#include<stdio.h>
// 定义最大元素数量
#include MAX_SIZE 1000
int parent[MAX_SIZE];
int uf_size;
// 初始化并查集
void initUnionFind(int n) {
    uf_size = n;
    for (int i = 0; i < uf_size; ++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 rootX = find(x);
    int rootY = find(y);
    if (rootX != rootY) {
        parent[rootY] = rootX;
    }
}
// 检查是否在同一集合
int isSameSet(int x, int y) {
    return find(x) == find(y);
}
// 重置并查集
void resetUnionFind() {
    for (int i = 0; i < uf_size; ++i) {
        parent[i] = i;
    }
}

2. 按秩合并优化

#include<iostream>
using namespace std;

int u[5100];
int rank_[5100]; // 用于按大小合并
int n, m, p;

// 初始化并查集
void init(int size) {
    for (int i = 1; i <= size; i++) {
        u[i] = i;       // 每个元素的父节点初始化为自身
        rank_[i] = 1;   // 每个集合的初始大小为1
    }
}

// 带路径压缩的查找
int f(int x) {
    if (u[x] != x) {
        u[x] = f(u[x]); // 路径压缩
    }
    return u[x];
}

// 按大小合并
void un(int x, int y) {
    int rootX = f(x);
    int rootY = f(y);
    if (rootX == rootY) return;
    // 小集合合并到大集合
    if (rank_[rootX] < rank_[rootY]) {
        u[rootX] = rootY;
        rank_[rootY] += rank_[rootX];
    } else {
        u[rootY] = rootX;
        rank_[rootX] += rank_[rootY];
    }
}