Number of Provinces
Count the provinces, groups of cities connected directly or through each other, in an adjacency matrix by running one DFS from every city not yet visited.
Problem Understanding
Number of Provinces (LeetCode 547): there are n cities, and isConnected[i][j] = 1 when cities i and j are directly connected. A province is a group of cities connected directly or through other cities, with no city outside the group connected to it. Return the number of provinces.
Examples: [[1,1,0],[1,1,0],[0,0,1]] → 2; [[1,0,0],[0,1,0],[0,0,1]] → 3.
The Intuition: One Province per Fresh Start
A province is a connected component of the city graph, so count components:
- Scan the cities in order.
- An unvisited city starts a new province. Every city in it is still unvisited, because none could have been reached before.
- DFS from it and mark everything it reaches, directly or through other cities.
The same counting idea on a grid is Number of Islands, and union-find counts the same components in Number of Operations to Make Network Connected.
Interactive Walkthrough
COLOUR = PROVINCE · GREEN = CONNECTION THE DFS WALKED
SCAN THE CITIES
city
:
provinces
0
7 cities, 4 direct connections. Scan the cities in order
Next
City 0 is not visited yet: it starts province 1. DFS from it
connections
n
Each DFS paints one province a colour; green edges are the connections it walked. Try Through others: two cities with no direct connection still end up in one province.
Dry Run Table
Input: 7 cities, connections 0-1, 1-3, 3-2, 4-5.
| Scan | Action | Provinces |
|---|---|---|
| city 0 | unvisited: start province 1, DFS reaches 1, 3, 2 | 1 |
| cities 1-3 | already visited | 1 |
| city 4 | unvisited: start province 2, DFS reaches 5 | 2 |
| city 5 | already visited | 2 |
| city 6 | unvisited: start province 3, no connections | 3 |
Answer: 3.
The Solution Template
A visited array and one DFS per unvisited city.
Number of Provinces Code
1var findCircleNum = function(isConnected) {2 const n = isConnected.length;3 const visited = new Array(n).fill(false);4 const dfs = (u) => {5 for (let v = 0; v < n; v++) {6 if (isConnected[u][v] && !visited[v]) {7 visited[v] = true;8 dfs(v);9 }10 }11 };12 let provinces = 0;13 for (let i = 0; i < n; i++) {14 if (!visited[i]) {15 provinces++;16 visited[i] = true;17 dfs(i);18 }19 }20 return provinces;21};
Edge Cases & Common Mistakes
- No connections (identity matrix): every city is its own province, the answer is n.
- Everything connected: one province.
- Counting direct connections only: cities joined through a third city are in the same province; the DFS must follow chains.
- Forgetting the diagonal: isConnected[i][i] is always 1, which is harmless because city i is already visited.
- Counting inside the DFS: count only at the start of each new DFS, not per visited city.
Summary
Scan the cities; each unvisited one starts a new province and a DFS over its matrix row marks everything reachable. The number of starts is the answer. O(n²) time, O(n) space.
More practice: DSA interview questions with answers · patterns cheat sheet