Number of Provinces
Given an adjacency matrix of cities, count the number of connected provinces (groups of directly/indirectly connected cities).
- 1 <= n <= 200
- n == isConnected.length
- n == isConnected[i].length
- isConnected[i][j] is 1 or 0.
- isConnected[i][i] == 1
- isConnected[i][j] == isConnected[j][i]
Intuition
Number of provinces counts groups of directly or indirectly connected cities, given an adjacency matrix rather than an edge list. A province is a connected component.
The matrix representation is the distinguishing feature. isConnected[i][j] == 1 means cities i and j are directly connected, and the matrix is symmetric since connections are mutual.
The counting logic is standard:
- Start a traversal from every unvisited city; each launch covers one entire province, so the launch count is the answer.
From a city, the neighbours are found by scanning its entire row — every j where the entry is 1. That row scan is what makes the traversal O(n) per city rather than proportional to the actual neighbour count.
Because every cell of the matrix is examined once across the whole traversal, the cost is O(n²) — unavoidable, since reading the input alone requires it.
The diagonal is always 1, as a city connects to itself. That is harmless: i is marked visited before its row is scanned, so the self-reference is skipped by the visited check without needing a special case.
Union-Find is equally valid — union every pair where the matrix holds 1, then count distinct roots. Same O(n²) cost, since all pairs must still be examined.
The symmetry means only the upper triangle strictly needs scanning for Union-Find, halving the constant factor but not the complexity.
This is Number of Connected Components with a different input format, and recognising that makes it routine.
Counting connected components: every unvisited vertex you encounter starts a new component, and one traversal claims everything reachable from it. The input is an adjacency matrix, so neighbours are found by scanning a row rather than following a list.
Approach
Before reading on: price up what the direct approach costs here, then ask whether you are really just merging groups and asking what connects. Aim for O(n^2) time and O(n) space.
Read the matrix format
isConnected[i][j] == 1 means cities i and j are directly connected, and the matrix is symmetric since connections are mutual.
Count traversal launches
Start a DFS or BFS from each unvisited city. Each launch covers one entire province, so the number of launches is the answer.
Find neighbours by row scan
From city i, scan its whole row for entries equal to 1. This costs O(n) per city regardless of the actual neighbour count.
Let the diagonal handle itself
Every city connects to itself, but marking i visited before scanning its row means the self-reference is skipped — no special case needed.
Or use Union-Find
Union every connected pair and count distinct roots. Only the upper triangle needs scanning thanks to symmetry, halving the constant factor.
Cost of the approach
Every matrix cell is examined once, giving O(n²) time — unavoidable, since reading the input alone requires it — with O(n) space for the visited array.
Solution & live demo
Common pitfalls
Incrementing inside the traversal
def dfs(u):
provinces += 1
...for i in range(n):
if not visited[i]:
provinces += 1
dfs(i)That counts vertices, not components. The increment belongs at the outer loop, where each execution marks the discovery of a region nothing before it could reach.
Marking visited after the neighbour loop
for v in ...: dfs(v) visited[u] = True
visited[u] = True for v in ...:
The matrix is symmetric, so u is its own neighbours' neighbour. Marking late means the recursion bounces back into u before the flag is set and never terminates.
Treating the matrix as an edge list
for v in isConnected[u]:
for v in range(n):
if isConnected[u][v] == 1 and not visited[v]:Iterating the row yields the 0/1 values themselves, not vertex indices, so the recursion descends into vertices 0 and 1 forever. The index is the neighbour; the value is only whether the edge exists.
Edge cases
Every city starts its own DFS, so provinces == n.
First DFS visits every city; provinces == 1.
One DFS call, provinces == 1.
Self-loops are ignored by skipping j == i during the scan; they never affect connectivity.