Number of Provinces

medium graph dfs

Problem

There are n cities. Some of them are connected, while some are not. If city a is connected directly with city b, and city b is connected directly with city c, then city a is connected indirectly with city c.

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 number_of_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 numberOfProvinces(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 numberOfProvinces(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 numberOfProvinces(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;
}

Explanation

A "province" is just a connected group of cities. So this problem is really asking us to count how many separate clusters exist in the friendship graph given by the matrix M.

We walk over every city i. If we have not seen it yet, it must be the start of a new province, so we do count += 1 and launch a depth-first search from it.

The dfs(u) marks u as seen, then visits every city v where M[u][v] is 1 and v is still unseen. This recursion floods through the whole cluster, marking every reachable city, so they are not counted again.

Example: M = [[1,1,0,0],[1,1,0,0],[0,0,1,1],[0,0,1,1]]. Start at city 0, DFS reaches 1 → that whole group is marked, count is 1. Next unseen city is 2; DFS reaches 3 → count is 2. Cities 1 and 3 were already marked, so they add nothing. Answer is 2.

Each new count bump corresponds to one untouched cluster, which is exactly the number of provinces.

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