AceYourInterviews
Checking sign-in…

109. Number of Provinces

CoreCount components while joining the upper triangle of an undirected matrix

Cities belong to the same province if a chain of direct city connections links them, even when they are not directly connected to one another. Count all resulting connected groups.

Include cities that are isolated from every other city. Connectivity is transitive, and the matrix's shape and symmetry requirements are part of the contract.

Example 1

Input

[[1,1,0],[1,1,0],[0,0,1]]

Output

2

Explanation: Cities 0 and 1 form one province; city 2 is an isolated province.

Example 2

Input

[[1,1,0],[1,1,1],[0,1,1]]

Output

1

Explanation: 0 and 2 need no direct edge: the path through 1 joins all three cities.

Example 3

Input

[[1,1,1],[1,1,1],[1,1,1]]

Output

1

Explanation: After two successful joins, the remaining upper-triangle connection is within an existing set.

Constraints

  • 0 <= n <= 1000
  • connected.length == connected[i].length == n
  • connected[i][j] is 0 or 1
  • The matrix is symmetric and diagonal entries are 1.
Hints
Hint 1

Every city begins as a separate province, including isolated indices.

Hint 2

Process each undirected connection once using the upper triangle.

Hint 3

Join distinct roots by size and reduce the province count only on a successful union.

Practice on LeetCode ↗
Code
Saved on this deviceLn 1, Col 1

One connected pair plus an isolated city

[[1,1,0],[1,1,0],[0,0,1]]
2