Count Connected Provinces

medium graph dfs

Problem

You are given an n × n symmetric matrix where M[i][j] = 1 means cities i and j are directly connected. A province is a maximal group of cities all reachable from one another. Return the number of provinces.

InputM = [[1,1,0,0],[1,1,0,0],[0,0,1,1],[0,0,1,1]]

Output2

Cities {0, 1} form one province and {2, 3} form another.

adjacency matrix (rows separated by ';', cells by ',')

def count_provinces(M):
    n = len(M)
    seen = [False] * n
    count = 0
    def dfs(u):
        seen[u] = True
        for v in range(n):
            if M[u][v] and not seen[v]:
                dfs(v)
    for i in range(n):
        if not seen[i]:
            count += 1
            dfs(i)
    return count

function countProvinces(M) {
  const n = M.length;
  const seen = new Array(n).fill(false);
  let count = 0;
  function dfs(u) {
    seen[u] = true;
    for (let v = 0; v < n; v++) if (M[u][v] && !seen[v]) dfs(v);
  }
  for (let i = 0; i < n; i++) if (!seen[i]) { count++; dfs(i); }
  return count;
}

class Solution {
    int n;
    int[][] M;
    boolean[] seen;
    public int countProvinces(int[][] M) {
        this.M = M;
        this.n = M.length;
        this.seen = new boolean[n];
        int count = 0;
        for (int i = 0; i < n; i++) if (!seen[i]) { count++; dfs(i); }
        return count;
    }
    private void dfs(int u) {
        seen[u] = true;
        for (int v = 0; v < n; v++) if (M[u][v] == 1 && !seen[v]) dfs(v);
    }
}

int n_;
vector<vector<int>> M_;
vector<bool> seen_;
void dfs(int u) {
    seen_[u] = true;
    for (int v = 0; v < n_; v++) if (M_[u][v] && !seen_[v]) dfs(v);
}
int countProvinces(vector<vector<int>>& M) {
    M_ = M;
    n_ = M.size();
    seen_.assign(n_, false);
    int count = 0;
    for (int i = 0; i < n_; i++) if (!seen_[i]) { count++; dfs(i); }
    return count;
}

Time: O(n²) Space: O(n)