#547 - Number of Provinces

MediumGraphs - DFS

There are n cities. isConnected[i][j] = 1 means city i and city j are directly connected. A province is a group of directly or indirectly connected cities. Return the number of provinces.

Input	Output
isConnected = [[1,1,0],[1,1,0],[0,0,1]]	2
isConnected = [[1,0,0],[0,1,0],[0,0,1]]	3

Solution Space

Try it

/**
 * Counts the number of connected components (provinces) in the city graph.
 *
 * @param isConnected n×n adjacency matrix
 * @returns Number of provinces
 */
export function findCircleNum(isConnected: number[][]): number {
  const n = isConnected.length;
  const visited = new Array<boolean>(n).fill(false);
  let provinces = 0;

  for (let i = 0; i < n; i++) {
    if (!visited[i]) {
      provinces++;
      dfs(i, isConnected, visited);
    }
  }

  return provinces;
}

function dfs(city: number, graph: number[][], visited: boolean[]): void {
  visited[city] = true;
  for (let j = 0; j < graph.length; j++) {
    if (graph[city][j] === 1 && !visited[j]) {
      dfs(j, graph, visited);
    }
  }
}

Approach: DFS connected components – iterate through all cities; for each unvisited city, increment the province count and DFS-flood-fill all connected cities.

Time: O(n²) – every cell in the adjacency matrix is checked.

Space: O(n) – visited array plus recursion stack.

Alternative approaches:

Approach	Idea	Time	Space
Union-Find	For each edge (i, j), union the two cities; count distinct roots at the end	O(n² · α(n)) ≈ O(n²)	O(n)
BFS	Same idea as DFS but use a queue	O(n²)	O(n)

Why DFS is preferred: simplest to implement for adjacency matrix input; Union-Find is better for edge-list representations.

#399 Evaluate Division

#841 Keys and Rooms