1060. Number of Provinces — Connected Components

Given an n x n matrix isConnected where isConnected[i][j] = 1 means cities i and j are directly connected, return the number of provinces — groups of directly or indirectly connected cities. The input is JSON {isConnected}.

Input: JSON {isConnected}.

Output: Integer — the number of provinces.

Examples

Input: {"isConnected":[[1,1,0],[1,1,0],[0,0,1]]}
Output: 2
Explanation: Cities 0,1 form one province; city 2 another.

Input: {"isConnected":[[1,0,0],[0,1,0],[0,0,1]]}
Output: 3
Explanation: All separate.

Input: {"isConnected":[[1]]}
Output: 1
Explanation: Single city.

Constraints

• 1<=n<=200

Asked by