62. Number of Provinces

class Solution:
    def findCircleNum(self, isConnected: List[List[int]]) -> int:
        n = len(isConnected)
        parent = list(range(n))
        def find(x):                          # with path compression
            while parent[x] != x:
                parent[x] = parent[parent[x]]
                x = parent[x]
            return x
        groups = n
        for i in range(n):
            for j in range(i + 1, n):
                if isConnected[i][j]:
                    a, b = find(i), find(j)
                    if a != b:
                        parent[a] = b         # union two provinces
                        groups -= 1
        return groups

class Solution {
    private int[] parent;
    private int find(int x) {
        while (parent[x] != x) { parent[x] = parent[parent[x]]; x = parent[x]; }
        return x;
    }
    public int findCircleNum(int[][] isConnected) {
        int n = isConnected.length, groups = n;
        parent = new int[n];
        for (int i = 0; i < n; i++) parent[i] = i;
        for (int i = 0; i < n; i++)
            for (int j = i + 1; j < n; j++)
                if (isConnected[i][j] == 1) {
                    int a = find(i), b = find(j);
                    if (a != b) { parent[a] = b; groups--; }
                }
        return groups;
    }
}

class Solution {
    vector<int> parent;
    int find(int x) {
        while (parent[x] != x) { parent[x] = parent[parent[x]]; x = parent[x]; }
        return x;
    }
public:
    int findCircleNum(vector<vector<int>>& isConnected) {
        int n = isConnected.size(), groups = n;
        parent.resize(n);
        iota(parent.begin(), parent.end(), 0);
        for (int i = 0; i < n; i++)
            for (int j = i + 1; j < n; j++)
                if (isConnected[i][j]) {
                    int a = find(i), b = find(j);
                    if (a != b) { parent[a] = b; groups--; }
                }
        return groups;
    }
};

function findCircleNum(isConnected) {
  const n = isConnected.length, parent = [...Array(n).keys()];
  const find = x => { while (parent[x] !== x) { parent[x] = parent[parent[x]]; x = parent[x]; } return x; };
  let groups = n;
  for (let i = 0; i < n; i++)
    for (let j = i + 1; j < n; j++)
      if (isConnected[i][j]) {
        const a = find(i), b = find(j);
        if (a !== b) { parent[a] = b; groups--; }
      }
  return groups;
}