Number of Provinces

Medium · Graphs · Explanation and code example

Disjoint Set Union

How it works

The Union-Find (Disjoint Set Union) data structure is designed for efficiently managing connected components. We start with each city as its own component. As we process connections, we union the components of connected cities. The final number of distinct components equals the number of provinces. Path compression and union by size optimizations make this approach nearly O(1) per operation.

Steps

  1. Initialize a DSU with n components, where each city is its own parent.
  2. For each pair of cities (i, j) where isConnected[i][j] == 1:
    • Call union(i, j) to merge their components.
    • The union operation decrements the component count if the cities were in different components.
  3. Return the final component count from the DSU.

Complexity

  • Time complexity: O(n ^ 2)
  • Space complexity: O(n)

Things to watch for

Confusing Nodes with Edges

The adjacency matrix isConnected[i][j] represents whether city i and city j are directly connected. A common mistake is treating the matrix indices as edge indices rather than node indices. Remember that n is the number of cities, not the number of connections.

Forgetting to Mark Nodes as Visited

When performing DFS or BFS, failing to mark a node as visited before or immediately after processing it can lead to infinite loops or counting the same province multiple times. Always mark nodes as visited as soon as they are encountered.

Misunderstanding the Diagonal

The diagonal elements isConnected[i][i] are always 1 (a city is connected to itself). When modifying the input to track visited status, be careful to use the diagonal correctly. Do not confuse self-connections with actual inter-city connections.

Python code example

from typing import List

class DSU:
    def __init__(self, n):
        self.Parent = list(range(n + 1))
        self.Size = [1] * (n + 1)
        self.components = n

    def find(self, node):
        if self.Parent[node] != node:
            self.Parent[node] = self.find(self.Parent[node])
        return self.Parent[node]

    def union(self, u, v):
        pu = self.find(u)
        pv = self.find(v)
        if pu == pv:
            return False

        self.components -= 1
        if self.Size[pu] >= self.Size[pv]:
            self.Size[pu] += self.Size[pv]
            self.Parent[pv] = pu
        else:
            self.Size[pv] += self.Size[pu]
            self.Parent[pu] = pv
        return True

    def numOfComps(self):
        return self.components

class Solution:
    def findCircleNum(self, isConnected: List[List[int]]) -> int:
        n = len(isConnected)
        dsu = DSU(n)

        for i in range(n):
            for j in range(n):
                if isConnected[i][j]:
                    dsu.union(i, j)

        return dsu.numOfComps()

C++ code example

class DSU {
public:
    vector<int> Parent, Size;
    int components;

    DSU(int n) {
        Parent.resize(n);
        Size.assign(n, 1);
        components = n;
        for (int i = 0; i < n; ++i) Parent[i] = i;
    }

    int find(int node) {
        if (Parent[node] != node)
            Parent[node] = find(Parent[node]);
        return Parent[node];
    }

    bool unionSet(int u, int v) {
        int pu = find(u), pv = find(v);
        if (pu == pv) return false;

        components--;
        if (Size[pu] >= Size[pv]) {
            Size[pu] += Size[pv];
            Parent[pv] = pu;
        } else {
            Size[pv] += Size[pu];
            Parent[pu] = pv;
        }
        return true;
    }

    int numOfComps() {
        return components;
    }
};

class Solution {
public:
    int findCircleNum(vector<vector<int>>& isConnected) {
        int n = isConnected.size();
        DSU dsu(n);
        for (int i = 0; i < n; ++i)
            for (int j = 0; j < n; ++j)
                if (isConnected[i][j])
                    dsu.unionSet(i, j);
        return dsu.numOfComps();
    }
};
Source and license

Adapted from NeetCode’s source · MIT license. Node types are supplied by LeetCode where needed.

Check the explanation on LeetCode

Your recall check is in progress. Write your attempt before revealing the explanation.

Resume recall check

Browse all problem explanations