547. Number of Provinces

class Solution {
    private static class UnionFind {
        private final int[] parent;
        private int count;

        public UnionFind(int n) {
            this.parent = new int[n];
            for (int i = 0; i < n; i++) {
                this.parent[i] = i;
            }
            this.count = n;
        }

        public void union(int x, int y) {
            int xRoot = getRoot(x);
            int yRoot = getRoot(y);
            if (xRoot != yRoot) {
                parent[xRoot] = yRoot;
                count--;
            }
        }

        private int getRoot(int x) {
            while (x != parent[x]) {
                parent[x] = parent[parent[x]];
                x = parent[x];
            }

            return x;
        }
    }

    public int findCircleNum(int[][] isConnected) {
        int n = isConnected.length;

        UnionFind unionFind = new UnionFind(n);
        for (int i = 0; i < isConnected.length; i++) {
            for (int j = 0; j < isConnected[i].length; j++) {
                if (isConnected[i][j] == 1) {
                    unionFind.union(i, j);
                }
            }
        }

        return unionFind.count;
    }
}

References

547. Number of Provinces
剑指 Offer II 116. 省份数量