Number of Provinces

mediumGraphs: Topological Sort & Union-Find58 stepsJava · Python · C++

Count connected groups of cities from an adjacency matrix. Start with every city as its own group; union the two groups of every connected pair. Each successful union merges two groups, so the answer is n minus the number of successful unions.

▶ Watch the animated trace

Traced input: isConnected = [[1, 1, 0, 0], [1, 1, 0, 0], [0, 0, 1, 1], [0, 0, 1, 1]] → 2. Original problem: neetcode.io/problems/number-of-provinces

Complexity

BestO(n² α(n))

AverageO(n² α(n))

WorstO(n² α(n))

SpaceO(n)

The matrix has n² entries; union-find operations are nearly O(1).

Key idea

parent[i] points toward the representative (root) of i's group.
find() follows parents to the root, compressing the path as it goes.
union() links one root under the other if they differ.
DFS over the matrix counting components works equally well.

Common mistakes

Forgetting path compression makes find() slow on long chains.
Counting roots without calling find() on each node first.

Solution

Java

int[] parent;

int find(int x) {
    if (parent[x] != x) parent[x] = find(parent[x]);
    return parent[x];
}

int findCircleNum(int[][] isConnected) {
    int n = isConnected.length, groups = n;
    parent = new int[n];
    for (int i = 0; i < n; i++) parent[i] = i;
    for (int i = 0; i < n; i++)
        for (int j = i + 1; j < n; j++) {
            if (isConnected[i][j] == 0) continue;
            int a = find(i), b = find(j);
            if (a != b) {
                parent[a] = b;
                groups--;
            }
        }
    return groups;
}

Python

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

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

    groups = n
    for i in range(n):
        for j in range(i + 1, n):
            if isConnected[i][j] == 0: continue
            a, b = find(i), find(j)
            if a != b:
                parent[a] = b
                groups -= 1
    return groups

C++

vector<int> parent;

int find(int x) {
    if (parent[x] != x) parent[x] = find(parent[x]);
    return parent[x];
}

int findCircleNum(vector<vector<int>>& isConnected) {
    int n = isConnected.size(), groups = n;
    parent.assign(n, 0);
    for (int i = 0; i < n; i++) parent[i] = i;
    for (int i = 0; i < n; i++)
        for (int j = i + 1; j < n; j++) {
            if (isConnected[i][j] == 0) continue;
            int a = find(i), b = find(j);
            if (a != b) {
                parent[a] = b;
                groups--;
            }
        }
    return groups;
}

Edge cases

Each one has its own trace in the interactive view.

Case	Input	Answer
No connections Every city is alone.	`isConnected = [[1, 0, 0], [0, 1, 0], [0, 0, 1]]`	`3`
All connected Two unions merge everything.	`isConnected = [[1, 1, 1], [1, 1, 1], [1, 1, 1]]`	`1`
Chain 0 and 2 are connected through 1.	`isConnected = [[1, 1, 0], [1, 1, 1], [0, 1, 1]]`	`1`
Single city One province.	`isConnected = [[1]]`	`1`