并查集

通用版

class UnionFind {
    int[] s;

    public UnionFind(int size) {
        s = new int[size];
        for (int i = 0; i < size; i++) {
            s[i] = i;
        }
    }

    public int find(int x) {
        int r = s[x];
        if (r != x) {
            r = find(s[x]);
        }

        return r;
    }

    public void union(int i, int j) {
        int iBoss = find(i);
        int jBoss = find(j);

        if (iBoss != jBoss) {
            if(iBoss < jBoss) {
                s[jBoss] = iBoss;
            } else {
                s[iBoss] = jBoss;
            }
        }
    }
}

hash表版（没有初始化节点(i -> i)，需要在外部主动初始化）

class UnionFind {
    Map<Integer, Integer> map = new HashMap<>();

    public UnionFind() {}

    public int find(int x) {
        int r = map.get(x);
        if(map.get(x) != x) {
            r = find(r);
        }

        return r;
    }

    public void union(int i, int j) {
        int iBoss = find(i);
        int jBoss = find(j);

        if (iBoss != jBoss) {
            if (iBoss < jBoss) {
                map.put(jBoss, iBoss);
            } else {
                map.put(iBoss, jBoss);
            }
        }
    }
}

完全版

有path compressed
有 union by rank

class DisjointSet {
    int[] s;
    int[] rank;

    public DisjointSet(int size) {
        s = new int[size];
        rank = new int[size];
        for (int i = 0; i < size; i++) {
            s[i] = i;
        }
    }

    public int find(int x) {
        // path compression
        if (s[x] != x) {
            s[x] = find(s[x]);
        }

        return s[x];
    }

    public void union(int i, int j) {
        int iBoss = find(i);
        int jBoss = find(j);

        if (iBoss != jBoss) {
            // union by rank
            if (rank[iBoss] < rank[jBoss]) {
                s[iBoss] = jBoss;
            } else if (rank[iBoss] > rank[jBoss]) {
                s[jBoss] = iBoss;
            } else {
                s[iBoss] = jBoss;
                rank[jBoss]++;
            }
        }
    }

    @Override
    public String toString() {
        return "DisjointSet{" +
            "s=" + Arrays.toString(s) +
            '}';
    }
}