并查集（联合查找数据结构）代码模板（C/C++/Java/Python多版本）

并查集，又被称为“联合查找数据结构”或“不相交集合数据结构”，是一种用于高效处理分组与连通性问题的数据结构，它支持快速合并两个集合（Union）和查询两个元素是否属于同一集合（Find）。其核心思想是用树结构代表集合，通过路径压缩和按秩合并两大优化，将操作时间降至近乎常数级别。并查集广泛应用于网络连接判定、最小生成树算法、朋友圈归类等需要动态维护元素关系的场景。

1. C/C++版代码：

// 并查集(路径压缩)
const int max_n = 100005;
int par[max_n];
void init(int n) { // 初始化
    for (int i = 1; i <= n; i++)
        par[i] = i;
}
int find(int x) { // 查找所在集合的根
    if (par[x] != x)
        par[x] = find(par[x]); // 递归返回的同时压缩路径
    return par[x];
}
void unite(int x, int y) { // 合并x与y所在集合
    x = find(x);
    y = find(y);
    par[x] = y;
}
bool same(int x, int y) { // x与y在同一集合则返回真
    return find(x) == find(y);
}

2. Java版代码：

// 并查集(路径压缩)
public class UnionFind {
    private static final int MAX_N = 100005;
    private int[] par = new int[MAX_N];
    
    // 初始化
    void init(int n) {
        for (int i = 1; i <= n; i++) 
            par[i] = i;
    }
    
    // 查找所在集合的根
    int find(int x) {
        if (par[x] != x) 
            par[x] = find(par[x]); // 递归返回的同时压缩路径
        return par[x];
    }
    
    // 合并x与y所在集合
    void unite(int x, int y) {
        x = find(x);
        y = find(y);
        par[x] = y;
    }
    
    // x与y在同一集合则返回真
    boolean same(int x, int y) {
        return find(x) == find(y);
    }
}

3. Python版代码：

# 并查集(路径压缩)
MAX_N = 100005
par = [0] * MAX_N
# 初始化
def init(n):
    for i in range(1, n + 1):
        par[i] = i
# 查找所在集合的根
def find(x):
    if par[x] != x:
        par[x] = find(par[x])  # 递归返回的同时压缩路径
    return par[x]
# 合并x与y所在集合
def unite(x, y):
    x = find(x)
    y = find(y)
    par[x] = y
# x与y在同一集合则返回真
def same(x, y):
    return find(x) == find(y)