Number of Provinces
There are n cities numbered 0 to n - 1. You are given an n × n matrix isConnected: isConnected[i][j] === 1 means a direct road joins city i and city j, and 0 means there is no direct road. Roads work in both directions, so the matrix is symmetric, and every city counts as connected to itself (isConnected[i][i] === 1).
Roads chain together. If city a has a road to b, and b has a road to c, then a and c are in the same group even without a direct road between them. A province is a group of cities that can all reach one another this way, and that no city outside the group can reach.
Return the number of provinces.
Constraints
1 <= n <= 200isConnected[i][j]is0or1isConnected[i][i] === 1andisConnected[i][j] === isConnected[j][i]
Examples
Example 1
Input: isConnected = [[1,1,0],[1,1,0],[0,0,1]] Output: 2
Cities 0 and 1 share a road, so they form one province. City 2 has no road to anyone and is a province on its own: 2 in total.
Example 2
Input: isConnected = [[1,0,0,1],[0,1,1,0],[0,1,1,0],[1,0,0,1]] Output: 2
Cities 0 and 3 are linked, and so are 1 and 2. Two provinces, even though the linked cities are not next to each other in the matrix.
Example 3
Input: isConnected = [[1,1,0,0],[1,1,1,0],[0,1,1,1],[0,0,1,1]] Output: 1
0-1, 1-2 and 2-3 are linked. City 0 reaches city 3 through 1 and 2, so all four cities form a single province.
JavaScript you'll use: Classes for data structures Arrays: create, read, update
/**
* @param {number[][]} isConnected
* @return {number}
*/
function findCircleNum(isConnected) {
}
Ctrl/⌘ + ' runs the examples, Ctrl/⌘ + Enter submits. Use console.log freely: output shows under Console. In the editor, press Esc then Tab to move focus out.