Graph Breadth First Search Depth First Search Shortest Path Minimum Spanning Tree
Intermediate Level

Implement the countProvincesUnionFind method that counts connected city groups from an adjacency matrix.

You are given an n x n matrix where connected[i][j] = 1 means city i and city j are directly connected.

A province is a group of cities that are directly or indirectly connected. Return the total number of provinces.

Example 1
Input:
connected (int[][]) = [[1,1,0],[1,1,0],[0,0,1]]
n (int) = 3
Return:
(int) 2
Example 2
Input:
connected (int[][]) = [[1,0,0],[0,1,0],[0,0,1]]
n (int) = 3
Return:
(int) 3
Example 3
Input:
connected (int[][]) = [[1,1,1],[1,1,1],[1,1,1]]
n (int) = 3
Return:
(int) 1

Use Union-Find to merge connected cities.

Initially, every city is its own province. For every pair of cities with value 1, union their sets. After all connections are processed, the number of unique roots gives the number of provinces.

This works because Union-Find naturally groups direct and indirect connections.

Pseudocode:

function countProvincesUnionFind(connected, n):
    initialize parent for n cities
    for i from 0 to n - 1:
        for j from i + 1 to n - 1:
            if connected[i][j] == 1:
                union(i, j)
    roots = empty set
    for city from 0 to n - 1:
        add find(city) to roots
    return size of roots
Run your code to see the result.