0547 Number of Provinces

0547 Number of Provinces.java

import java.util.*;

class Solution {
    private int[] root;
    private int[] rank;

    public int findCircleNum(int[][] edges) {
        int n = edges.length;
        root = new int[n];
        rank = new int[n];
        Arrays.fill(rank, 1);

        for (int i = 0; i < n; i++)
            root[i] = i;

        for (int i = 0; i < n; i++)
            for (int j = i + 1; j < n; j++)
                if (edges[i][j] == 1)
                    union(i, j);
        
        Set<Integer> res = new HashSet<>();
        for (int i = 0; i < n; i++)
            res.add(find(i));
        
        return res.size();

    }

    private int find(int i) {
        int r = root[i];
        while (r != root[r]) {
            root[r] = root[root[r]];
            r = root[r];
        }
        root[i] = r;
        return r;
    }

    private void union(int x, int y) {
        int rx = find(x);
        int ry = find(y);
        if (rx == ry) {
            return;
        }
        if (rank[rx] >= rank[ry]) {
            rank[rx] += rank[ry];
            root[ry] = rx;
        } else {
            rank[ry] += rank[rx];
            root[rx] = ry;
        }
    }
}