Saved from https://leetcode.com/problems/number-of-provinces/submissions/

lc547

class Solution {
    // A typical union-find problem
    // Time: O(n^2 logn)
    // Space: O(n)
    public int findCircleNum(int[][] isConnected) {
        int n = isConnected.length;
        UnionFind uf = new UnionFind(n);
        for (int i = 0; i < n - 1; i++) {
            for (int j = i + 1; j < n; j++) {
                if (isConnected[i][j] == 1) {
                    uf.union(i, j);
                }
            }
        }
        return uf.componentCnt;
    }
    
    // Weighted-quick-union algorithm
    // Guarantee worst cast O(logn) time for union and find operation
    public static class UnionFind {
        int[] ids;
        int[] sizes;
        int componentCnt;
        
        public UnionFind(int n) {
            ids = new int[n];
            sizes = new int[n];
            Arrays.fill(sizes, 1);
            for (int i = 0; i < n; i++) {
                ids[i] = i;
            }
            componentCnt = n;
        }
        
        // Time: log(n)
        public int find(int i) {
            while(ids[i] != i) {
                i = ids[i];
            }
            return  i;
        }
        
        // Time: log(n)
        public void union(int p, int q) {
            int pid = find(p);
            int qid = find(q);
            if (pid == qid) {
                return;
            }
            if (sizes[pid] > sizes[qid]) {
                ids[qid] = pid;
                sizes[pid] += sizes[qid];
            } else {
                ids[pid] = qid;
                sizes[qid] += sizes[pid];
            }
            componentCnt--;
        }
    }
}