Official 2044 views

Editorial: Number of Provinces

by admin · Oct. 18, 2026

1 Intuition

Count connected components.

2 Approach

Union-find: start with n groups and merge on every link, decrementing the count when two different groups join. DFS works too.

3 Complexity Analysis

Time O(n² · α(n)), Space O(n).

4 Solution Code

class Solution:
    def findCircleNum(self, isConnected: list[list[int]]) -> int:
        n = len(isConnected)
        parent = list(range(n))
        def find(x):
            while parent[x] != x:
                parent[x] = parent[parent[x]]
                x = parent[x]
            return x
        groups = n
        for i in range(n):
            for j in range(i + 1, n):
                if isConnected[i][j]:
                    a, b = find(i), find(j)
                    if a != b:
                        parent[a] = b
                        groups -= 1
        return groups

5 Code Walkthrough

The reference solution below implements the approach step by step.