Pattern visualizer

Number of Provinces

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. 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?.

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

time O(n^2)space O(n)step 1 / 14

Cities and direct connections, no province labels yet

line 1

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

Where to practice Graph

Practice Graph problems All Graph problems Back to roadmap