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.

Example 1:

Input: isConnected = [[1,1,0,0],[1,1,1,0],[0,1,1,0],[0,0,0,1]]
Output: 2
Explanation: cities 0, 1, and 2 form one province; city 3 is its own province.

Example 2:

Input: isConnected = [[1,0,0,0,0],[0,1,0,0,0],[0,0,1,0,0],[0,0,0,1,0],[0,0,0,0,1]]
Output: 5
Explanation: no two cities are connected, so each city is its own province.

Example 3:

Input: isConnected = [[1,1],[1,1]]
Output: 1
Explanation: every city is connected to every other, so there is a single province.

Constraints:

• 1 <= n <= 100
• n == isConnected.length
• n == isConnected[i].length
• isConnected[i][j] is 1 or 0.
• isConnected[i][i] == 1
• isConnected[i][j] == isConnected[j][i]

Solution Breakdown

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,0],[1,1,1,0],[0,1,1,0],[0,0,0,1]]: start components = 4. Cell (0,1) is 1, so union(0, 1) merges them and drops the count to 3. Cell (1,2) is 1, so union(1, 2) drops the count to 2. All cells involving city 3 are 0, so city 3 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.