Count how many connected components exist in an undirected graph described by an adjacency matrix.
You are given an adjacency matrix isConnected for an undirected graph with n cities. If isConnected[i][j] = 1, city i and city j are directly connected; otherwise they are not.
A province is a group of cities that are directly or indirectly connected, and no city outside the group is connected to them.
Return the number of provinces in the graph.
You may solve this using graph traversal or a disjoint set approach.
isConnected.isConnected where isConnected[i][j] is 0 or 1.isConnected[i][i] = 1 for all valid i.isConnected.length == nisConnected[i].length == nisConnected[i][j] is either 0 or 1isConnected[i][j] == isConnected[j][i]isConnected[i][i] == 1Example 1
Input
isConnected = [[1,1,0],[1,1,0],[0,0,1]]
Output
2
Explanation
Cities 0 and 1 form one connected component, and city 2 forms another. So there are 2 provinces.
Example 2
Input
isConnected = [[1,0,0],[0,1,0],[0,0,1]]
Output
3
Explanation
No city is connected to any other city, so each city is its own province.
Premium problem context
Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.