412. Number of Provinces
There are n cities numbered 0 through n − 1, and you receive an n × n matrix isConnected where isConnected[i][j] = 1 means cities i and j share a direct road (0 means they don't). The matrix is symmetric and every city connects to itself.
Reachability chains: if a links to b and b links to c, then a, b, and c can all reach each other. A province is a maximal set of cities that are mutually reachable this way.
Return the number of provinces as a single integer.
Example 1:
Input: isConnected = [[1,1,0],[1,1,0],[0,0,1]]
Output: 2
Explanation: Cities 0 and 1 share a road, so they form one province; city 2 stands alone as the second.
Example 2:
Input: isConnected = [[1,0,0],[0,1,0],[0,0,1]]
Output: 3
Explanation: No roads at all — each city is its own province.
Constraints:
- 1 ≤ n ≤ 200
- isConnected[i][j] is 0 or 1
- isConnected[i][i] = 1 and isConnected[i][j] = isConnected[j][i]
Hints:
This is connected components in disguise: cities are vertices, 1-entries are edges, and a province is one component.
Flood fill works: start at an unvisited city, DFS/BFS through the matrix marking everything reachable, and count how many times you had to start over.
Union-Find counts components without any traversal: union i and j for every 1-entry, and the answer is the number of elements that are still their own root.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: isConnected = [[1,1,0],[1,1,0],[0,0,1]]
Expected output: 2