Number of Provinces Using Graph Traversal

Problem Statement❯

Given an undirected graph with V vertices represented as an adjacency matrix isConnected, a province is a group of directly or indirectly connected cities (vertices). A city is connected to itself.

Your task is to determine the total number of such provinces (i.e., the number of connected components in the graph).

Examples❯

isConnected (Adjacency Matrix)	Number of Provinces	Description
[[1,1,0],[1,1,0],[0,0,1]]	2	Cities 0 and 1 form one province, city 2 forms another.
[[1,0,0],[0,1,0],[0,0,1]]	3	Each city is isolated, hence 3 provinces.
[[1,1,1],[1,1,1],[1,1,1]]	1	All cities are connected, so only one province.
[[1]]	1	Only one city, so one province.
[]	0	No cities, hence no province.

Solution❯

Understanding the Problem

The problem involves identifying how many disconnected groups of cities exist, where a direct or indirect connection means two cities belong to the same group. These groups are known as 'provinces' in this context, and they represent the number of connected components in an undirected graph.

Case 1: All Cities Are Isolated

If none of the cities are connected to any other (i.e., the adjacency matrix has only 1s on the diagonal and 0s elsewhere), then each city is its own province. In this case, the number of provinces is equal to the number of cities.

Case 2: All Cities Are Fully Connected

If every city is connected either directly or through a chain of connections to every other city, then the graph is a single connected component. So the answer is 1 province.

Case 3: Multiple Connected Groups

When the graph has multiple subsets of cities where each subset is internally connected but disconnected from other subsets, each subset forms its own province. The algorithm identifies each such group through DFS or BFS, marking visited cities to avoid recounting.

Step-by-Step Traversal

The traversal (either DFS or BFS) starts from each unvisited city. If a city has not been visited, a new traversal begins from that city and marks all reachable cities as visited. This entire traversal corresponds to one province. Once all cities are checked, the total count of such traversals equals the number of provinces.

Algorithm Steps❯

Initialize a visited array of size V with all values set to false.
Initialize provinceCount = 0.
For each city i from 0 to V-1:

If visited[i] is false:

Perform DFS/BFS starting from i.
Mark all connected cities as visited.
Increment provinceCount.

Return provinceCount.

Code

JavaScript

function findCircleNum(isConnected) {
  const n = isConnected.length;
  const visited = new Array(n).fill(false);

  function dfs(city) {
    for (let neighbor = 0; neighbor < n; neighbor++) {
      if (isConnected[city][neighbor] === 1 && !visited[neighbor]) {
        visited[neighbor] = true;
        dfs(neighbor);
      }
    }
  }

  let provinces = 0;

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

  return provinces;
}

console.log("Provinces:", findCircleNum([[1,1,0],[1,1,0],[0,0,1]])); // Output: 2
console.log("Provinces:", findCircleNum([[1,0,0],[0,1,0],[0,0,1]])); // Output: 3

Time Complexity❯

Case	Time Complexity	Explanation
Best Case	O(V + E)	Even if all cities are in a single province, DFS/BFS will still visit all vertices and edges to ensure full connectivity.
Average Case	O(V + E)	Each node and edge is visited once across all connected components using DFS or BFS.
Worst Case	O(V + E)	In the worst case (e.g., each city is isolated), we still visit every node and no edges, resulting in a traversal of size V.

Space Complexity❯

O(V)

Explanation: A visited array of size V is required to track which cities have already been checked during traversal.

⬅ Previous TopicDepth-First Search in Graphs

Next Topic ⮕Connected Components in a Matrix