MediumDepth-First SearchBreadth-First SearchUnion FindGraph

Number of Provinces

1 approach, code in every language

There are n cities, some of which are directly connected to one another. A province is a group of cities that are connected either directly or indirectly, with no city outside the group belonging to it.

You are given an n x n matrix isConnected, where isConnected[i][j] = 1 means city i and city j are directly connected and isConnected[i][j] = 0 means they are not. Note that the matrix is symmetric and every city is connected to itself.

Return the total number of provinces.

Example 1

Input: isConnected = [[1,1,0],[1,1,0],[0,0,1]]

Output: 2

Cities 0 and 1 are connected, forming one province, while city 2 stands alone as a second province.

Example 2

Input: isConnected = [[1,0,0],[0,1,0],[0,0,1]]

Output: 3

No two distinct cities are connected, so each city is its own province.

Constraints

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

Union-Find (Disjoint Set Union)

Union every connected pair read from the matrix, then count how many distinct roots remain.

Loading animation…

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

1Read n from the matrix dimension and set up a parent array plus a counter equal to n.
2Iterate over pairs (i, j) with j > i so each unordered pair is checked once.
3When isConnected[i][j] equals 1, find the roots of i and j.
4If the roots differ, union the two cities and decrement the counter.
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

Time

O(n^2 * α(n))

Space

O(n)

Every one of the n^2 matrix cells is visited once, and each union/find is near-constant amortized, so the scan dominates.

Create a free account to see the solution

You get the step-by-step animation, the intuition and clean code in every language. Free, no credit card.

Create a free account Already have an account? Sign in

Back to Graphs

After the pattern

Now solve one you haven't seen.

Count the Sensor Meshes is our own problem on the technique behind Number of Provinces: a new statement, so there's no answer to remember. Write it in your browser and run it against graded tests.

Practise it with tests All practice problems

1,194 problems · 15,062 graded tests · free