Number of Provinces

There are n cities. Some of them are connected, while some are not. If city a is connected directly with city b, and city b is connected directly with city c, then city a is connected indirectly with city c.

A province is a group of directly or indirectly connected cities and no other cities outside of the group.

You are given an n x n matrix isConnected where isConnected[i][j] = 1 if the i^th city and the j^th city are directly connected, and isConnected[i][j] = 0 otherwise.

Return the total number of provinces.

Input:

First Parameter - matrix isConnected of size m x n

Output:

Return the total number of provinces.

Example 1

Input:
3 3
1 1 0
1 1 0
0 0 1
Output:
2
Explanation: This 3 3 matrix represent the connection between the cities, as we can see value of 1st raw and 2nd column is 1,This means city 1 and city 2 are connected so this collectively form one province and city 3 individually behaving as province. Then, total provinces are 2.

Example 2

Input:
3 3
1 0 0
0 1 0
0 0 1
Output:
3
Explanation:  In This matrix of connection no cities are connected but they are individually behaving as province ,so there are total 3 province.

Constraints:

• 1 <= n <= 200
• n == isConnected.length
• n == isConnected[i].length
• isConnected[i][j] is 1 or 0.
• isConnected[i][i] == 1
• isConnected[i][j] == isConnected[j][i]
• Expected Time Complexity: O(n^2)
• Expected Auxiliary Space: O(n)