#547

Medium

auto_awesomeGraph traversal with depth-first search

LeetCode Problem Workspace

Number of Provinces

Solve Number of Provinces by scanning the adjacency matrix and launching DFS once per unvisited city component.

depth first search breadth first search union find graph

Problem Statement

You are given an n x n adjacency matrix named isConnected where each row and column represents a city. A value of 1 means two cities share a direct connection, and a value of 0 means they do not. Because connections can chain through intermediate cities, cities can still belong to the same group even when they are not directly linked to each other.

A province is one maximal set of cities connected by any path in the matrix. Your job is to count how many such groups exist. For example, isConnected = [[1,1,0],[1,1,0],[0,0,1]] forms one province from cities 0 and 1 and another from city 2, so the correct answer is 2.

Examples

Example 1

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

Output: 2

Example details omitted.

Example 2

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

Output: 3

Example details omitted.

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]

Solution Approach

Model the matrix as an undirected graph

Treat each city as a node and each 1 in isConnected[i][j] as an undirected edge. Since the matrix is symmetric and isConnected[i][i] is always 1, you do not need to build a separate adjacency list. You can traverse neighbors directly by scanning row i when exploring city i.

Count components with depth-first search

Maintain a visited array of length n. Loop through every city, and when you find one that has not been visited, increment the province count and run DFS from that city. The DFS scans the city's row, visits every connected neighbor, and keeps expanding until the full connected component has been marked.

Know the equivalent alternatives

Breadth-first search produces the same province count with a queue instead of recursion or an explicit stack. Union Find also works by merging every pair of connected cities, then counting distinct roots at the end. For this problem's matrix input, DFS is usually the most direct explanation because it maps cleanly to connected-components traversal without extra structure.

Complexity Analysis

Metric	Value
Time	O(n^2)
Space	O(n)

The time complexity is O(n^2) because each DFS expansion scans an entire matrix row, and across the full run you inspect matrix entries in an n by n grid. The space complexity is O(n) for the visited array, plus recursion stack or an explicit stack in the worst case when one province contains every city.

What Interviewers Usually Probe

They want connected components, not shortest paths, because the question asks for grouped cities rather than route length.
The adjacency matrix format hints that scanning rows directly is expected, so building another graph structure is often unnecessary overhead.
If they ask for DFS, BFS, and Union Find trade-offs, they are checking whether you can recognize equivalent component-counting strategies on the same input.

Common Pitfalls or Variants

Common pitfalls

Incrementing the province count for every connected edge instead of for every new unvisited starting city gives the wrong answer.
Forgetting indirect connectivity leads to under-grouping, especially when city 0 connects to 1 and city 1 connects to 2.
Revisiting cities because visited is marked too late can cause repeated work or infinite recursion on dense parts of the matrix.

Follow-up variants

Return the actual province members instead of only the count by collecting cities during each DFS.
Switch the input from an adjacency matrix to an edge list, which changes neighbor lookup and usually favors adjacency lists or Union Find.
Handle dynamic connection updates, where Union Find becomes more attractive than rerunning full DFS after each merge.

FAQ

What is the best approach for Number of Provinces?

Depth-first search is usually the best interview answer because the problem is asking for the number of connected components in an adjacency matrix. You scan each city once, launch DFS from every unvisited city, and count how many launches you make.

Why does DFS work for the graph traversal pattern in Number of Provinces?

DFS fully explores one city group before returning, so one DFS call marks exactly one province. When the outer loop finds another unvisited city later, that city must belong to a different province.

Can I use BFS instead of DFS here?

Yes. BFS is equivalent for counting provinces because it also explores one connected component at a time. The main difference is queue-based traversal instead of recursion or an explicit stack.

When is Union Find a good choice for this problem?

Union Find is a strong alternative when you naturally think in terms of merging connected city pairs. It is especially useful when the problem evolves into repeated union operations, but for the given matrix input DFS is often simpler to explain and code.

Why is the time complexity O(n^2) instead of O(n + e)?

The input is an n x n adjacency matrix, so neighbor discovery requires scanning matrix rows. Even if the graph is sparse, you still inspect entries across the matrix, which makes the practical cost O(n^2) for Number of Provinces.

terminal

Solution

Solution 1: DFS

We create an array $\textit{vis}$ to record whether each city has been visited.

class Solution:
    def findCircleNum(self, isConnected: List[List[int]]) -> int:
        def dfs(i: int):
            vis[i] = True
            for j, x in enumerate(isConnected[i]):
                if not vis[j] and x:
                    dfs(j)

        n = len(isConnected)
        vis = [False] * n
        ans = 0
        for i in range(n):
            if not vis[i]:
                dfs(i)
                ans += 1
        return ans

Solution 2: Union-Find

We can also use the union-find data structure to maintain each connected component. Initially, each city belongs to a different connected component, so the number of provinces is $n$.

class Solution:
    def findCircleNum(self, isConnected: List[List[int]]) -> int:
        def dfs(i: int):
            vis[i] = True
            for j, x in enumerate(isConnected[i]):
                if not vis[j] and x:
                    dfs(j)

        n = len(isConnected)
        vis = [False] * n
        ans = 0
        for i in range(n):
            if not vis[i]:
                dfs(i)
                ans += 1
        return ans

Continue Practicing

#684 redundant connection #685 redundant connection ii #399 evaluate division