Number of Provinces — Counting Connected Components with DFS and Union Find

Problem Statement#

There are n cities, some of which are directly connected. The relationship is given by an n by n matrix isConnected where isConnected[i][j] equals 1 if city i and city j are directly linked and 0 otherwise. The matrix is symmetric and the diagonal is always 1. A province is a group of cities that are directly or indirectly connected. Return the total number of provinces.

This is a connected-components count on an undirected graph represented as an adjacency matrix.

Why This Problem Matters#

Number of Provinces is the textbook example of how interviewers verify that you understand graph traversal beyond a simple BFS or DFS template. It shows up at Amazon, Microsoft, Bloomberg, and many FAANG-adjacent companies because it tests three skills at once: representing a graph from an adjacency matrix, traversing connected components with either BFS or DFS, and reasoning about Union Find as an alternative when the graph is dense or when you need incremental connectivity queries.

It is also a stepping stone to harder problems such as Number of Islands, Friend Circles in social networks, Account Merge, and Redundant Connection. Companies frequently follow up this question with a streaming variant where edges arrive one at a time, which is where Union Find truly shines.

The Core Insight#

A province is a connected component. If you start a DFS or BFS from any unvisited city and mark every city you can reach, you have explored exactly one province. Increment a counter for each new traversal you launch from an unvisited node, and at the end the counter equals the number of provinces.

Because the input is an adjacency matrix, neighbors of node i are simply the column indices j where isConnected[i][j] equals 1, so checking neighbors is an O(n) scan per node. The total work is O(n squared), which matches the matrix size and is optimal for dense input.

Union Find approaches the same problem from the opposite direction: treat every city as its own province, then for every pair (i, j) with isConnected[i][j] equal to 1 union the two cities. The province count starts at n and decrements by one each time a successful union merges two distinct sets.

Visual Dry Run (BFS/DFS trace)#

Consider four cities with the matrix that has 1s on the diagonal, 1 between cities 0 and 1, 1 between cities 1 and 2, and 0 between city 3 and any other city. We start with count equal to 0 and visited all false.

Iteration on city 0. It is unvisited, so we launch DFS, push 0 onto the stack, and mark visited[0] true. We scan row 0; column 1 is connected and unvisited, so DFS into city 1. Mark visited[1] true. We scan row 1; column 0 is connected but visited, column 2 is connected and unvisited, so DFS into city 2. Mark visited[2] true. We scan row 2; column 1 is connected but visited. The DFS unwinds. We bump count to 1 because the launch from city 0 just discovered an entire province containing 0, 1, and 2.

Iteration on city 1. Already visited, skip.

Iteration on city 2. Already visited, skip.

Iteration on city 3. Unvisited, launch DFS. We mark visited[3] true. Row 3 has no connections beyond the self-loop. The DFS finishes immediately. We bump count to 2.

The answer is 2 provinces. Notice how the for-loop over the cities is what isolates separate components; the DFS itself only explores within one province.

Solution (Optimal)#

Python — DFS#

class Solution:
    def findCircleNum(self, isConnected):
        n = len(isConnected)
        visited = [False] * n
 
        def dfs(i):
            visited[i] = True
            for j in range(n):
                if isConnected[i][j] == 1 and not visited[j]:
                    dfs(j)
 
        count = 0
        for i in range(n):
            if not visited[i]:
                dfs(i)
                count += 1
        return count

JavaScript — Union Find#

var findCircleNum = function(isConnected) {
    const n = isConnected.length;
    const parent = Array.from({ length: n }, (_, i) => i);
    const find = (x) => {
        while (parent[x] !== x) {
            parent[x] = parent[parent[x]];
            x = parent[x];
        }
        return x;
    };
    let count = n;
    for (let i = 0; i < n; i++) {
        for (let j = i + 1; j < n; j++) {
            if (isConnected[i][j] === 1) {
                const a = find(i), b = find(j);
                if (a !== b) {
                    parent[a] = b;
                    count--;
                }
            }
        }
    }
    return count;
};

DFS time complexity is O(n squared) because we examine every cell of the matrix; space is O(n) for the visited array plus the recursion stack. Union Find runs in O(n squared times alpha of n), which is effectively O(n squared) due to the inverse Ackermann factor; space is O(n) for the parent array.

Common Mistakes#

Treating the matrix as a list of edges instead of an adjacency matrix and trying to build an adjacency list first wastes memory and time. Forgetting to mark a node visited before recursing causes infinite recursion on the first cycle. Counting cities instead of components by incrementing inside the DFS is a classic off-by-many error; the increment must live in the outer loop. Using Union Find without path compression on a dense matrix can degrade to O(n cubed) on adversarial inputs. Iterating both j less than n and j not equal to i for the symmetric matrix when you can stop at j greater than i doubles the Union Find work unnecessarily.

Interview Tips#

Open by reframing the question: this is connected-components count. State the two viable approaches (DFS or BFS, and Union Find) and pick DFS for clarity unless the interviewer hints at streaming edges. Verbalize the invariant that a fresh DFS launch from an unvisited node always discovers a new component. Remember to discuss complexity in terms of the matrix size, not edges, because the matrix forces O(n squared) regardless of how sparse the actual graph is. Mention the iterative BFS variant if asked about recursion depth on n up to 200.

Follow-up Questions#

What if the input is a list of edges instead of an adjacency matrix? Build an adjacency list and run the same DFS in O(V plus E). What if cities and friendships arrive over a stream and you need the current province count after each event? Union Find shines here; each insert is amortized constant time. How would you list the cities inside each province? Modify the DFS to collect nodes and store the resulting groups. What if the relationship is asymmetric, like one-way phone calls? Then the question becomes strongly connected components, which requires Tarjan or Kosaraju.

Key Takeaways#

• Number of Provinces is the canonical connected-components problem on an adjacency matrix
• DFS or BFS both work; the outer for-loop is what counts components, not the traversal itself
• Union Find is the right answer for streaming edges or when components are queried repeatedly
• Adjacency matrices force O(n squared) work even when the graph is sparse
• Always mark visited before recursing to prevent infinite loops on cycles
• The pattern unlocks Number of Islands, Account Merge, Friend Circles, and Redundant Connection