Number of Provinces

1class Solution {
2    public int findCircleNum(int[][] isConnected) {
3        int n = isConnected.length;
4        int[] parent = new int[n];
5        int[] size = new int[n];
6        int provinces = n;
7
8        for (int i = 0; i < n; i++) {
9            parent[i] = i;
10            size[i] = 1;
11        }
12
13        for (int i = 0; i < n; i++) {
14            for (int j = i + 1; j < n; j++) {
15                if (isConnected[i][j] == 1) {
16                    int rootI = find(parent, i);
17                    int rootJ = find(parent, j);
18
19                    if (rootI != rootJ) {
20                        union(parent, size, rootI, rootJ);
21                        provinces--;
22                    }
23                }
24            }
25        }
26
27        return provinces;
28    }
29
30    private int find(int[] parent, int x) {
31        if (parent[x] != x) {
32            parent[x] = find(parent, parent[x]);
33        }
34        return parent[x];
35    }
36
37    private void union(int[] parent, int[] size, int x, int y) {
38        if (size[x] < size[y]) {
39            parent[x] = y;
40            size[y] += size[x];
41        } else {
42            parent[y] = x;
43            size[x] += size[y];
44        }
45    }
46}