Java高阶数据结构-----并查集（详解）

并查集是一种树型的数据结构，用于处理一些不交集的合并及查询问题。它主要支持两种操作：

1. union(x, y)：把元素 x 和元素 y 所在的集合合并，要求 x 和 y 所在的集合不相交。
2. isConnected(x, y)：判断元素 x 和元素 y 是否属于同一个集合。

并查集可以用一个数组来实现，数组中的每个元素都存储了它的父节点的信息。如果一个元素的父节点是它自己，说明它是一个集合的代表元素，也就是根节点。

下面是一个简单的并查集的实现：

public class UnionFind {
    private int[] parent; // 记录每个节点的父节点
 
    public UnionFind(int size) {
        parent = new int[size];
        for (int i = 0; i < size; i++) {
            parent[i] = i; // 初始时每个元素的父节点是自己
        }
    }
 
    // 查找元素x的根节点
    private int find(int x) {
        if (parent[x] != x) {
            parent[x] = find(parent[x]); // 路径压缩
        }
        return parent[x];
    }
 
    // 合并元素x和元素y所在的集合
    public void union(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);
        if (rootX != rootY) {
            parent[rootX] = rootY; // 将一个集合的根节点连接到另一个集合的根节点
        }
    }
 
    // 判断元素x和元素y是否属于同一个集合
    public boolean isConnected(int x, int y) {
        return find(x) == find(y);
    }
}

使用方法：

UnionFind uf = new UnionFind(10); // 初始化并查集，有10个元素
uf.union(0, 1); // 合并元素0和元素1所在的集合
uf.union(2, 3);
boolean connected = uf.isConnected(0, 2); // 判断元素0和元素2是否属于同一个集合

这个简单的实现支持路径压缩，即在find操作中，我们会把路径上的每个节点直接连接到根节点，以减少查找时间。