Number of Provinces

Given an adjacency matrix isConnected, return the number of provinces. A province is a connected component in an undirected graph. Use DSU find operations to compress representative lookups while merging related cities.

Input Format

isConnected = adjacency matrix

Output Format

number of provinces

Constraints

  • 1 <= input size <= 10^5
  • -10^9 <= numeric values <= 10^9
  • Input must satisfy the format described in inputFormat.

Examples

Example 1:

Input:

isConnected = [[1,1,0],[1,1,0],[0,0,1]]

Output:

2

Explanation:

Cities 0 and 1 are connected, while city 2 is isolated.

Example 2:

Input:

isConnected = [[1]]

Output:

1

Explanation:

One city means one province.

Example 3:

Input:

isConnected = [[1,0],[0,1]]

Output:

2

Explanation:

No cities are connected, so each city is its own province.

Loading...
Number of Provinces - Union Find DSA Problem