Number of Provinces

Intuition

A province is simply a connected component expressed through an adjacency matrix rather than an edge list. Because the matrix is symmetric, scanning only the upper triangle with j > i visits every undirected link exactly once. Feeding those links into Union-Find groups mutually reachable cities under a shared root. Starting from n singleton cities and merging on each genuine link, the number of remaining groups equals the province count.

Algorithm walkthrough

1. 1Read n from the matrix dimension and set up a parent array plus a counter equal to n.
2. 2Iterate over pairs (i, j) with j > i so each unordered pair is checked once.
3. 3When isConnected[i][j] equals 1, find the roots of i and j.
4. 4If the roots differ, union the two cities and decrement the counter.
5. 5Return the counter after the full scan; it holds the number of provinces.

Implementation

class Solution:
    def findCircleNum(self, isConnected: List[List[int]]) -> int:
        n = len(isConnected)
        parent = list(range(n))

        def find(x: int) -> int:
            while parent[x] != x:
                parent[x] = parent[parent[x]]
                x = parent[x]
            return x

        count = n
        for i in range(n):
            for j in range(i + 1, n):
                if isConnected[i][j] == 1:
                    ri, rj = find(i), find(j)
                    if ri != rj:
                        parent[ri] = rj
                        count -= 1
        return count