Number of Provinces
Medium · Union Find · Graph · Union Find · DFS · BFS
Problem
isConnected[i][j] == 1 means city i and city j are directly linked. A province is a group of cities connected directly or indirectly, and connected to no city outside it.
Return how many provinces there are.
Examples
Input: isConnected = [[1,1,0],[1,1,0],[0,0,1]] Output: 2
Cities 0 and 1 form one province; city 2 stands alone.
Input: isConnected = [[1,0,0],[0,1,0],[0,0,1]] Output: 3
No links at all.
Constraints
- 1 <= n <= 200
- isConnected[i][i] == 1
- isConnected[i][j] == isConnected[j][i]
Approaches
- Flood fill from each unvisited city — time O(n²), space O(n)
Related problems
Start free on Cariara · Coding problems · System design studio
