Description
There are n cities. Some are connected directly, some indirectly, and some not at all. A province is a group of connected cities. Return the total number of provinces.
Examples
Input:
isConnected = [[1,1,0],[1,1,0],[0,0,1]]Output:
2Explanation:
Cities 0 and 1 form one province, city 2 is another.
Input:
isConnected = [[1,0,0,1],[0,1,1,0],[0,1,1,0],[1,0,0,1]]Output:
2Explanation:
There are 4 cities total. Cities 0 and 3 are directly connected to each other, forming one province. Cities 1 and 2 are directly connected to each other, forming another province. So there are 2 provinces in total.
Input:
isConnected = [[1,1,1,1,1],[1,1,1,1,1],[1,1,1,1,1],[1,1,1,1,1],[1,1,1,1,1]]Output:
1Explanation:
All 5 cities are directly connected to every other city, meaning they all belong to the same province. Therefore, there is only 1 province total.
Constraints
- •
1 ≤ n ≤ 200 - •
isConnected[i][j] is 0 or 1