Number of Provinces

Problem

A province is a group of cities that are directly or indirectly connected. You are given an n x n adjacency matrix where isConnected[i][j] = 1 means city i and city j are directly connected. Return the total number of provinces.

isConnected = [[1,1,0],[1,1,0],[0,0,1]]  →  2
isConnected = [[1,0,0],[0,1,0],[0,0,1]]  →  3
isConnected = [[1,1,1],[1,1,1],[1,1,1]]  →  1

Solution

Approach - Union-Find with a running component count.

Every city starts as its own province, so components begins at n and parent[i] = i. The matrix is symmetric and the diagonal is always 1, so we only scan the strict upper triangle (j in range(i + 1, n)) - that visits each undirected edge once and skips the self-loops that would corrupt the count. For each is_connected[i][j] == 1, we call union(i, j). The key move lives in union: it finds both roots, and if they already match it returns without touching components; otherwise it links the shorter tree under the taller (union by rank) and decrements components by one. Because a tree of k nodes is built by exactly k - 1 merges, the count that survives all unions is precisely the number of provinces.

Trace [[1,1,0],[1,1,0],[0,0,1]]: start components = 3. Cell (0,1) is 1, so union(0, 1) merges them and drops the count to 2. Cells (0,2) and (1,2) are 0, so city 2 stays alone. Final answer 2. Path compression in find flattens each lookup so repeated finds during the n^2 scan stay near-constant.

Edge cases - A single city [[1]] runs no union iterations and returns 1. The fully-isolated identity matrix never unions, returning n; the all-ones matrix merges everything down to 1.

Complexity - O(n^2 * alpha(n)) time - we inspect all n^2 cells, each union near-constant. O(n) space for the parent and rank arrays.