noodleProblems/
Number of Provinces
#106

Number of Provinces

AlgorithmmediumGraphUnion FindDepth First SearchBreadth First SearchMatrix

You are given an n x n **adjacency matrix** isConnected describing direct connections between n cities. isConnected[i][j] === 1 means city i and city j are directly connected, and isConnected[i][j] === 0 means they are not.

A **province** is a group of cities that are connected either directly or indirectly (through other cities), where no city outside the group is connected to any city inside it — in graph terms, a connected component.

Return the total number of provinces.

The matrix is symmetric (isConnected[i][j] === isConnected[j][i]) and every city is connected to itself (isConnected[i][i] === 1).

Example cases

  • two provinces
    in isConnected =
    110
    110
    001
    out 2
    Cities 0 and 1 are directly connected, forming one province. City 2 is isolated, forming a second.
  • all isolated
    in isConnected =
    100
    010
    001
    out 3
    No city is connected to any other, so each of the 3 cities is its own province.
  • indirect connection
    in isConnected =
    110
    111
    011
    out 1
    0–1 and 1–2 are directly connected, so 0 and 2 are connected indirectly through 1 — one province.

Constraints

  • 1 <= n <= 200
  • n === isConnected.length === isConnected[i].length
  • isConnected[i][j] is 0 or 1
  • isConnected[i][i] === 1
  • isConnected[i][j] === isConnected[j][i]
Saved
isConnected =
[[1,1,0],[1,1,0],[0,0,1]]