Number of Provinces (Connected Components)
Medium · Graphs · about 20 minutes
Asked at Amazon, Google, Bloomberg, DoorDash.
There are n cities. isConnected[i][j] = 1 if cities i and j are directly connected, else 0 (the matrix is symmetric with 1s on the diagonal). A province is a group of cities connected directly or indirectly. Return the number of provinces.