并查集java数组实现

并查集是一种常用的数据结构，用于处理集合分组的问题，常用于解决查找、合并等操作。在Java中，可以使用数组来实现基本版的并查集，它通常包含两个主要部分：

1. **Disjoint Set**（不相交集合）：一个数组`parent`，每个元素i的值表示i所属的集合的根节点索引。如果`parent[i] == i`，则i是其自身的根。

2. **Union By Rank**（按秩合并）和**Path Compression**（路径压缩）策略：
- **Union**: 如果需要将集合A和B合并，找到两个集合的根节点`rootA = findSet(A)`和`rootB = findSet(B)`。如果`rootA != rootB`，则将秩较高（即`parent[rootA]`或`parent[rootB]`较小的那个的秩加一）的集合的根指向另一个集合的根。
- **Find Set**: 使用递归遍历`parent[]`数组，直到找到`parent[i] == i`为止，返回的就是根节点索引。

下面是简单的Java数组实现示例：

class DisjointSet {
    private int[] parent;
    private int rank;

    public DisjointSet(int n) {
        parent = new int[n];
        Arrays.fill(parent, -1); // 初始化所有元素为它们自己的根
        rank = 0; // 初始秩都是0
    }

    public int findSet(int i) {
        if (parent[i] < 0) return i; // 如果是根节点，则直接返回
        parent[i] = findSet(parent[i]); // 否则继续找根
        return parent[i];
    }

    public void union(int a, int b) {
        int rootA = findSet(a);
        int rootB = findSet(b);

        if (rootA == rootB) return; // 如果已经是同一集合，无需合并

        if (rank[rootA] > rank[rootB]) { // 根据秩合并
            parent[rootB] = rootA;
        } else {
            parent[rootA] = rootB;
            if (rank[rootA] == rank[rootB]) rank[rootB]++;
        }
    }
}

// 示例：
DisjointSet ds = new DisjointSet(5);
ds.union(0, 1); // 合并A和B
ds.union(3, 4); // 可能会形成A-B-C-D-E或A-B-C-E的结构
int connected = ds.findSet(2); // 查找2是否与其他已合并的节点相连