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.
Input Format
- An integer represented implicitly by the size of
isConnected. - A square matrix
isConnectedwhereisConnected[i][j]is0or1. - The matrix is symmetric and
isConnected[i][i] = 1for all validi.
Output Format
- Return a single integer: the number of connected components in the graph.
Constraints
isConnected.length == nisConnected[i].length == nisConnected[i][j]is either0or1isConnected[i][j] == isConnected[j][i]isConnected[i][i] == 1
Example 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
Unlock deeper context for this problem
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.