AlgoMaster Logo

Number of Provinces

mediumFrequency7 min readUpdated June 23, 2026

Understanding the Problem

This problem is counting connected components in an undirected graph. Each city is a node, and isConnected[i][j] = 1 means there is an edge between node i and node j. A "province" is another word for a connected component: a maximal set of nodes where you can reach any node from any other node through some path.

The input is an adjacency matrix, not an adjacency list. To find the neighbors of city i, scan row i and collect every column j where isConnected[i][j] = 1 and j != i (every city is connected to itself, which is not a useful edge).

The question reduces to: how many separate groups of cities exist? Start at any unvisited city and explore all cities reachable from it. That covers one complete province. The number of times you have to start a fresh exploration equals the number of provinces.

Key Constraints:

  • 1 <= n <= 200 → The matrix has at most 40,000 entries. Any O(n^2) approach reading the full matrix is the natural fit, and there is no reason to push for anything faster.
  • isConnected[i][j] == isConnected[j][i] → The graph is undirected, so an edge between i and j can be processed from either side.
  • isConnected[i][i] == 1 → The diagonal is always set. These self-loops are skipped, since a city in its own province does not connect it to anything new.

Approach 1: DFS (Depth-First Search)

Intuition

Start at a city you have not visited and explore as far as you can, visiting every city reachable from it. Once no new cities are reachable, one complete province has been found. Look for the next unvisited city and repeat. The number of fresh DFS traversals you start equals the number of provinces.

This is the connected components algorithm. The visited array prevents counting the same city twice: a DFS only starts from cities that no earlier traversal reached, so each province is counted exactly once.

Algorithm

  1. Create a visited boolean array of size n, initialized to false.
  2. Initialize provinces = 0.
  3. For each city i from 0 to n - 1:
    • If city i has not been visited, start a DFS from city i and increment provinces.
    • The DFS marks city i as visited, then recursively visits all unvisited neighbors of i.
  4. To find neighbors of city i, scan row i of the matrix: city j is a neighbor if isConnected[i][j] == 1 and j != i.
  5. Return provinces.

Example Walkthrough

1Initialize: visited = [false, false, false], provinces = 0
0
false
i
1
false
2
false
1/6

Code

DFS uses recursion, so a long chain of connected cities can drive the call stack to O(n) depth. The next approach explores the same components iteratively.

Approach 2: BFS (Breadth-First Search)

Intuition

BFS explores the same components as DFS, but iteratively. Instead of recursing into one path, it uses a queue to expand outward from the starting city, marking neighbors as visited as they are enqueued. The component-counting logic is unchanged: each fresh BFS that starts from an unvisited city is one more province.

BFS uses an explicit queue instead of the call stack, which removes the O(n) recursion depth that DFS can hit on a long chain of connected cities.

Algorithm

  1. Create a visited boolean array of size n, initialized to false.
  2. Initialize provinces = 0.
  3. For each city i from 0 to n - 1:
    • If city i has not been visited, start a BFS from city i and increment provinces.
    • BFS: add i to a queue, mark it visited. While the queue is not empty, dequeue a city, scan its row for unvisited neighbors, and enqueue them.
  4. Return provinces.

Example Walkthrough

1Initialize: visited = [false, false, false], provinces = 0
0
false
i
1
false
2
false
1/6

Code

DFS and BFS both traverse the graph to discover components. The next approach counts components without traversal, by merging connected cities into groups as it scans the edges.

Approach 3: Union Find

Intuition

Union Find (also called Disjoint Set Union) processes each edge and merges the two cities it connects into the same set. At the end, the number of distinct sets equals the number of provinces.

Start with each city in its own set, so the count of sets is n. For each connection isConnected[i][j] = 1, merge the sets containing city i and city j. A merge that joins two previously separate sets reduces the count by 1; if the two cities are already in the same set, nothing changes. Tracking that running count avoids a separate pass at the end: after all edges are processed, the count is the number of provinces, because two cities end up in the same set exactly when a path of edges connects them.

Path compression and union by rank are two standard optimizations that keep the find and union operations close to O(1) amortized.

Algorithm

  1. Initialize a parent array where parent[i] = i (each city is its own root).
  2. Initialize a rank array of all zeros (used for union by rank).
  3. Set provinces = n (initially each city is its own province).
  4. For each pair (i, j) where i < j and isConnected[i][j] == 1:
    • Find the root of city i and city j.
    • If the roots are different, merge them (union) and decrement provinces.
  5. Return provinces.

Example Walkthrough

1Initialize: parent = [0, 1, 2], each city is its own root. provinces = 3
0
0
1
1
2
2
1/5

Code