The problem
You are given an n×n matrix where isConnected[i][j] = 1 means city i and city j are directly connected. A province is a group of directly or indirectly connected cities. Return how many provinces exist.
Stuck? Reveal hints one at a time
How to approach it
- 1Keep a visited array of size n.
- 2Loop over every city i from 0 to n−1.
- 3If city i is unvisited, increment the province counter and run a DFS/BFS from it, marking every reachable city visited.
- 4Reachability check: from city c, every j with isConnected[c][j] === 1 is a neighbor.
- 5Return the counter — each DFS launch equals one component.
Key insight
Counting connected components = counting how many times you must "restart" a traversal before all nodes are visited.
The solution
Watch out for
- Forgetting that the matrix is symmetric and diagonal entries are 1 — neither breaks DFS, but do not double-count.
- Union-Find also works and shines if connections arrive as a stream of edges instead of a matrix.