Union Find Impl - rFronteddu/general_wiki GitHub Wiki

static class UnionFind {
    private int[] parent;
    private int[] rank;

    public UnionFind(int size) {
        parent = new int[size];
        rank = new int[size];
        for (int i = 0; i < size; i++) {
            // each node is its own parent
            parent[i] = i;
            // initial rank
            rank[i] = 1;
        }
    }

    public int find(int city) {
        if (parent[city] != city) {
            // path compression
            parent[city] = find(parent[city]);
        }
        return parent[city];
    }

    public void union(int city1, int city2) {
        int root1 = find(city1);
        int root2 = find(city2);
        
        if (root1 != root2) {
            // union by rank
            if (Rank[root1] > rank[root2]) {
                parent[root2] = root1;
            } else if (rank[root1] < rank[root2]) {       
                parent[root1] = root2;
            } else {
                parent[root2] = root1;
                rank[root1]++;
            }
        }
    }
}