LeetCode 547 - Number of Provinces

The problem is asking us to determine the number of provinces in a network of cities. Each city can be connected directly to other cities, and indirectly through chains of connections.

leetcodemediumdepth-first-searchbreadth-first-searchunion-findgraph-theory

LeetCode Problem 547

Difficulty: 🟡 Medium
Topics: Depth-First Search, Breadth-First Search, Union-Find, Graph Theory

Solution

Problem Understanding

The problem is asking us to determine the number of provinces in a network of cities. Each city can be connected directly to other cities, and indirectly through chains of connections. A province is defined as a set of cities that are all directly or indirectly connected, and that has no connections to cities outside the set.

The input is an n x n adjacency matrix isConnected, where isConnected[i][j] is 1 if city i and city j are directly connected, and 0 otherwise. Each city is always connected to itself, so the diagonal of the matrix is always 1. The output is a single integer representing the total number of provinces.

Constraints indicate that n can be up to 200, so a solution with O(n^3) complexity might be borderline acceptable, but O(n^2) or better is preferable. The matrix is symmetric, and cities are always connected to themselves, which simplifies traversal and ensures we do not need to check for invalid indices.

Important edge cases include fully connected cities (1 province), completely disconnected cities (each city is its own province), and the minimal case of a single city (1 province).

Approaches

The brute-force approach would be to consider each city and attempt to traverse all paths to other cities recursively or iteratively, keeping track of which cities have been visited. For each unvisited city, we would start a traversal to mark all cities in its province. This works because each province corresponds to a connected component in the graph. However, naive implementations may repeatedly check connections, resulting in O(n^3) time complexity if recursion explores all paths multiple times.

The optimal approach uses either Depth-First Search (DFS), Breadth-First Search (BFS), or Union-Find. These methods efficiently identify connected components:

  • DFS/BFS: For each unvisited city, perform DFS or BFS to mark all reachable cities as visited. Each traversal identifies exactly one province. Time complexity is O(n^2) because every matrix cell may be visited at most once.
  • Union-Find: Treat each city as a node in a disjoint-set forest. Union connected cities. The number of disjoint sets at the end is the number of provinces. Union-Find with path compression achieves nearly linear time in practice, O(n^2 * α(n)).
Approach Time Complexity Space Complexity Notes
Brute Force O(n^3) O(n) Traversal from each city with repeated visits leads to higher time complexity
DFS / BFS O(n^2) O(n) Visits each city and edge once
Union-Find O(n^2 * α(n)) O(n) Uses disjoint-set operations, efficient for repeated unions

Algorithm Walkthrough

We will describe the DFS approach in detail:

  1. Initialize a visited list of length n to track which cities have been explored.

  2. Initialize a province_count to 0.

  3. Iterate over each city i from 0 to n-1.

  4. If city i has not been visited:

  5. Increment province_count by 1 because starting a DFS here means a new province.

  6. Perform DFS starting at city i:

  • Mark the city as visited.
  • For each city j, if isConnected[i][j] == 1 and j is not visited, recursively visit city j.
  1. After iterating all cities, return province_count.

Why it works: Each DFS traversal fully explores a connected component of the graph. Since each province corresponds to a connected component, counting DFS starts on unvisited cities counts all provinces exactly once.

Python Solution

from typing import List

class Solution:
    def findCircleNum(self, isConnected: List[List[int]]) -> int:
        n = len(isConnected)
        visited = [False] * n

        def dfs(city: int):
            visited[city] = True
            for neighbor in range(n):
                if isConnected[city][neighbor] == 1 and not visited[neighbor]:
                    dfs(neighbor)

        province_count = 0
        for i in range(n):
            if not visited[i]:
                province_count += 1
                dfs(i)

        return province_count

This implementation first creates a visited array to keep track of explored cities. The dfs function marks the current city as visited and recursively visits all directly connected, unvisited cities. The main loop increments province_count whenever it finds an unvisited city, ensuring each connected component is counted once.

Go Solution

func findCircleNum(isConnected [][]int) int {
    n := len(isConnected)
    visited := make([]bool, n)

    var dfs func(int)
    dfs = func(city int) {
        visited[city] = true
        for neighbor := 0; neighbor < n; neighbor++ {
            if isConnected[city][neighbor] == 1 && !visited[neighbor] {
                dfs(neighbor)
            }
        }
    }

    provinceCount := 0
    for i := 0; i < n; i++ {
        if !visited[i] {
            provinceCount++
            dfs(i)
        }
    }

    return provinceCount
}

The Go version mirrors the Python implementation, using slices for visited and a recursive dfs function defined as a closure to allow recursion.

Worked Examples

Example 1:

Input: [[1,1,0],[1,1,0],[0,0,1]]

Step through DFS:

City Visited Action
0 [True, False, False] DFS to 1
1 [True, True, False] DFS ends
2 [True, True, True] DFS for new province

Output: 2

Example 2:

Input: [[1,0,0],[0,1,0],[0,0,1]]

All cities are disconnected, each DFS finds one province:

Output: 3

Complexity Analysis

Measure Complexity Explanation
Time O(n^2) Each cell in the adjacency matrix is visited at most once in DFS
Space O(n) Visited array and call stack for recursion up to n depth

Test Cases

# Provided examples
assert Solution().findCircleNum([[1,1,0],[1,1,0],[0,0,1]]) == 2  # two provinces
assert Solution().findCircleNum([[1,0,0],[0,1,0],[0,0,1]]) == 3  # three provinces

# Single city
assert Solution().findCircleNum([[1]]) == 1

# Fully connected cities
assert Solution().findCircleNum([[1,1,1],[1,1,1],[1,1,1]]) == 1

# Two provinces
assert Solution().findCircleNum([[1,1,0,0],[1,1,0,0],[0,0,1,1],[0,0,1,1]]) == 2

# Disconnected city in middle
assert Solution().findCircleNum([[1,1,0],[1,1,0],[0,0,1]]) == 2
Test Why
[[1,1,0],[1,1,0],[0,0,1]] Tests basic connectivity and indirect connections
[[1,0,0],[0,1,0],[0,0,1]] Tests completely disconnected cities
[[1]] Tests minimal input
[[1,1,1],[1,1,1],[1,1,1]] Tests fully connected graph, 1 province
[[1,1,0,0],[1,1,0,0],[0,0,1,1],[0,0,1,1]] Tests multiple separate components
[[1,1,0],[1,1,0],[0,0,1]] Repetition of basic example, ensures algorithm consistency

Edge Cases

Single City: When n=1, the algorithm correctly returns 1 since the DFS is invoked once and terminates immediately.

Completely Disconnected Graph: When all cities are disconnected except self-connections, each city forms its own province. DFS ensures each city is counted separately, and no recursion goes beyond the single city.

Fully Connected Graph: When all cities are connected to each other, DFS visits every city starting from the first one. Subsequent iterations skip visited cities, ensuring the province count is exactly 1. This validates that the implementation does not overcount.