Number of Provinces

DFS from every unvisited city, reading the adjacency matrix row by row

time O(n^2)space O(n)

A province is whatever a single DFS from one city can reach, so the algorithm never has to look for the groups directly — it only has to make sure every city gets visited once. Walk the cities in order; whenever one has not been visited yet, that is proof it belongs to a group nobody has explored, so start a fresh DFS from it and count one more province. Cities 0 and 2 have no direct matrix entry but both end up in the same province, because 1 chains them together — the badge on each city is the province number it was assigned, and the side panel is the DFS stack for whichever province is currently being explored.

Details

Animated on: 6 cities with adjacency matrix rows [1,1,0,0,0,0], [1,1,1,0,0,0], [0,1,1,0,0,0], [0,0,0,1,1,0], [0,0,0,1,1,0], [0,0,0,0,0,1] (isConnected[i][j] = 1 means i and j are directly connected) — how many provinces are there?

Problem:Number of ProvincesMedium

Pattern:Union Find

DFS from every unvisited city, reading the adjacency matrix row by row

step 1 / 14

Cities and direct connections, no province labels yet

6 cities and an n x n matrix where a 1 means the two cities are directly connected. 0 and 2 have no direct entry, but both connect through 1 — so a province is not just direct neighbours, it is everything reachable by chaining connections together.

Pseudocode

1FUNCTION numProvinces(isConnected, n):
2  visited <- ARRAY OF n FALSE
3  count <- 0
4  FOR i FROM 0 TO n - 1
5    IF visited[i] CONTINUE
6    count <- count + 1
7    stack <- [i]
8    visited[i] <- true
9    WHILE stack NOT EMPTY
10      u <- REMOVE LAST FROM stack
11      FOR j FROM 0 TO n - 1
12        IF isConnected[u][j] = 1 AND NOT visited[j]
13          visited[j] <- true
14          APPEND j TO stack
15  RETURN count

← / → step · space play · Home restart

Every step in words

Show all 14 steps

6 cities and an n x n matrix where a 1 means the two cities are directly connected. 0 and 2 have no direct entry, but both connect through 1 — so a province is not just direct neighbours, it is everything reachable by chaining connections together.
City 0 has not been visited, so it starts province #1. Push it and mark it visited.
Pop 0. Matrix row 0 marks 1 as directly connected — 1 is new, so mark it province #1 and push it.
Pop 1. Matrix row 1 marks 0, 2 as directly connected — 2 is new, so mark it province #1 and push it.
Pop 2. Matrix row 2 marks 1 as directly connected, but it is already visited — nothing new to push.
The stack is empty — province #1 is exactly {0, 1, 2}.
City 3 has not been visited, so it starts province #2. Push it and mark it visited.
Pop 3. Matrix row 3 marks 4 as directly connected — 4 is new, so mark it province #2 and push it.
Pop 4. Matrix row 4 marks 3 as directly connected, but it is already visited — nothing new to push.
The stack is empty — province #2 is exactly {3, 4}.
City 5 has not been visited, so it starts province #3. Push it and mark it visited.
Pop 5. Row 5 of the matrix has no other 1s — it connects to nobody else, so the stack stays exactly as it was.
The stack is empty — province #3 is exactly {5}.
Every city is visited and 3 separate DFS sweeps were needed to cover them all. RETURN 3.

Now solve it yourself

Watching is the first half. The second is writing it without the animation.

Solve Number of Provinces in the editor All Graph problems Back to roadmap