Diwali Offer!Flat 20% OFF
Enroll Now
PrakalpanaLive online tech training

150. Number of Provinces

MediumDay 44 of 60Graphs

There are n cities. isConnected[i][j] = 1 means cities i and j are directly connected, and 0 means they are not. Connection is transitive: if a connects to b and b connects to c, then a and c are in the same group. A province is a group of cities connected directly or indirectly, with no other city outside the group. Return the number of provinces.

Example 1
Input: isConnected = [[1,1,0],[1,1,0],[0,0,1]]
Output: 2
Cities 0 and 1 form one province and city 2 is alone.
Example 2
Input: isConnected = [[1,0,0],[0,1,0],[0,0,1]]
Output: 3
Constraints
  • 1 <= n <= 200
  • isConnected[i][j] is 0 or 1
  • isConnected[i][i] = 1
  • isConnected[i][j] = isConnected[j][i]
Hints
Frequently asked at: Amazon, Google, Goldman Sachs, Bloomberg
Ctrl + Enter runs the examples

Not sure what to learn next?

A 1-on-1 session with an industry mentor and a roadmap built for you. How it works

  1. 1Discuss your goals
  2. 2Get a personal plan
  3. 3Start learning
Book for ₹200/ 30 min