并查集的Java实现

以下是并查集的Java实现示例：

class UnionFind {
    private int[] parent;
    private int[] rank;
    
    public UnionFind(int size) {
        this.parent = new int[size];
        this.rank = new int[size];
        
        // 初始化每个元素为独立的集合，父节点为自身，秩为0
        for (int i = 0; i < size; i++) {
            parent[i] = i;
            rank[i] = 0;
        }
    }
    
    // 查找元素所属的集合（根节点）
    public int find(int x) {
        if (parent[x] != x) {
            // 路径压缩，将节点直接连接到根节点
            parent[x] = find(parent[x]);
        }
        return parent[x];
    }
    
    // 合并两个集合
    public void union(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);
        
        if (rootX == rootY) {
            return;
        }
        
        // 按秩合并，将较小的树合并到较大的树上
        if (rank[rootX] < rank[rootY]) {
            parent[rootX] = rootY;
        } else if (rank[rootX] > rank[rootY]) {
            parent[rootY] = rootX;
        } else {
            parent[rootY] = rootX;
            rank[rootX]++;
        }
    }
    
    // 判断两个元素是否属于同一个集合
    public boolean isConnected(int x, int y) {
        return find(x) == find(y);
    }
}

使用示例：

public class Main {
    public static void main(String[] args) {
        UnionFind uf = new UnionFind(5);
        
        uf.union(0, 1);
        uf.union(2, 3);
        uf.union(3, 4);
        
        System.out.println(uf.isConnected(1, 4));  // true
        System.out.println(uf.isConnected(0, 2));  // false
    }
}

以上是一个简单的并查集实现，通过调用 `union()` 方法合并集合，调用 `isConnected()` 方法判断两个元素是否属于同一个集合。