A state has n cities. Some pairs of cities have a direct bus route between them. You can also travel from one city to another by changing buses at the cities in between.
A group is a set of cities. You can travel between any two cities of the set. You can not travel to a city outside the set.
The grid isConnected shows the direct routes. isConnected[i][j] is 1 if city i and city j have a direct bus route. It is 0 if they do not.
Return the number of groups.
Examples
Example 1:
Input: isConnected = [[1,1,0,0],[1,1,0,0],[0,0,1,1],[0,0,1,1]]
Output: 2
Explanation: Cities 0 and 1 are joined to each other. Cities 2 and 3 are joined to each other. No bus links the two pairs, so there are 2 groups.
Example 2:
Input: isConnected = [[1,0,0],[0,1,0],[0,0,1]]
Output: 3
Explanation: Every city is joined only to itself. So each city is a group of its own.
Example 3:
Input: isConnected = [[1,1,0,0,0],[1,1,1,0,0],[0,1,1,0,0],[0,0,0,1,1],[0,0,0,1,1]]
Output: 2
Explanation: City 0 links to 1, and city 1 links to 2. So cities 0, 1 and 2 are one group, even though 0 and 2 have no direct bus. Cities 3 and 4 form the other group.