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. Return the total number of provinces.

30:00

Number of Provinces
medium
Topics
Companies

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. Return the total number of provinces.

Example 1:
Input: [[1,1,0],[1,1,0],[0,0,1]]
Output: 2
Constraints:

  • 1≤n≤2001 \leq n \leq 200

  • n==isConnected.length==isConnected[i].lengthn == \text{isConnected.length} == \text{isConnected}[i].\text{length}

  • isConnected[i][j]∈{0,1}\text{isConnected}[i][j] \in \{0, 1\}

  • isConnected[i][i]==1\text{isConnected}[i][i] == 1

  • isConnected[i][j]==isConnected[j][i]\text{isConnected}[i][j] == \text{isConnected}[j][i]

Input
arr =[[1,1,0],[1,1,0],[0,0,1]]

Initialize: 3 cities, find connected provinces

0

1

2

Adjacency Matrix

1

1

0

1

1

0

0

0

1

Provinces Found:

0

Variables
No variables to display
DepthFunction Call
Stack empty
0/5