Domain 2MediumCORE

Number of Provinces

We are given an adjacency matrix representing n cities where a value of 1 indicates a direct connection between two cities and 0 means no connection. The goal is to count the number of 'provinces.' A province is defined as a connected component in this graph—meaning all nodes within it can reach each other directly or indirectly, but cannot reach any node outside that group.

Domain: Medium•Updated: 2026-08-31
#Algorithms#LeetCode#qwen3.5:9b#Depth-first Search#Union Find

547. Number of Provinces

Model: qwen3.5:9b
Topics: Depth-first Search,Union Find
FAANG asked: 1
Acceptance rate: 60.7%


Problem Breakdown

We are given an adjacency matrix representing n cities where a value of 1 indicates a direct connection between two cities and 0 means no connection. The goal is to count the number of “provinces.” A province is defined as a connected component in this graph—meaning all nodes within it can reach each other directly or indirectly, but cannot reach any node outside that group.

Inputs:

  • isConnected: An N×NN \times N matrix where rows and columns represent cities (0 to N−1N-1).
  • Constraints: Matrix is symmetric (i,j == j,i) and diagonal elements are 1 (self-loops, which don’t affect component count logic but confirm a node exists).

Outputs:

  • An integer representing the total number of disjoint connected components.

Implicit Considerations:

  • Since NN can be up to 200, an algorithm with complexity better than linear relative to input size (O(N3)O(N^3)) is preferred over Floyd-Warshall or repeated BFS from every node without state management.
  • We must handle the transitive nature of connections (A connects B, B connects C →\rightarrow A connects C).

Intuition

The core task here is finding Connected Components in an undirected graph.

If I were to approach this naively, one might think: “I’ll check every pair of cities and see if they are connected.” However, connectivity is transitive. Checking pairs directly doesn’t account for indirect paths efficiently without a traversal structure. A brute-force attempt would be running a search (like BFS) from every node to count reachability, which leads to O(N3)O(N^3) time complexity because we repeat work on already visited nodes.

The key insight is that once I visit a city and explore all its neighbors recursively or iteratively, every reachable city in that province becomes “visited.” If I encounter an unvisited city later during my iteration through the matrix rows, it must belong to a new, distinct province because if it were connected to any previously visited node, we would have marked it as visited already.

Therefore, the strategy is: Iterate through each city. If it hasn’t been explored yet, start a traversal (DFS/BFS) from there and mark everything reachable in that component. The number of times I initiate this new traversal equals the total provinces.

Approach

  1. Initialize State: Create a visited array or set to track which cities have been processed. Initialize a counter for provinces at 0.
  2. Iterate Cities: Loop through each city index from 00 to n−1n-1.
  3. Check Visited Status: If the current city is not in visited:
    • Increment province count (we found a new component).
    • Start a Depth-First Search (DFS) or Breadth-First Search (BFS) from this city.
  4. Traverse Component: During DFS, for every neighbor connected to the current node:
    • If not visited, mark as visited and recurse/queue them.
  5. Return Result: After iterating all cities, return the count.

I chose an adjacency matrix traversal directly rather than converting to an adjacency list because NN is small (200), so accessing isConnected[i][j] in constant time during DFS avoids overhead of building a graph structure that isn’t strictly necessary for performance here. However, I will use recursion with a helper function for clarity and conciseness.

Complexity Analysis

  • Time Complexity: O(N2)O(N^2). We iterate through each city once (NN). For every unvisited node we start DFS which visits all reachable nodes. In the worst case (fully connected graph), we visit every edge in the matrix exactly once during traversal checks. Since there are N×NN \times N entries, and checking neighbors takes proportional time to row length, total operations scale with input size squared.
  • Space Complexity: O(N)O(N). We use a visited array of size NN. Additionally, DFS uses recursion stack space which is at most depth NN, so it remains linear relative to the number of cities.

Solution

class Solution:
    def findCircleNum(self, isConnected: List[List[int]]) -> int:
        n = len(isConnected)
        visited = [False] * n
        
        # Helper function for DFS traversal
        def dfs(city):
            stack = [city]
            while stack:
                curr = stack.pop()
                if not visited[curr]:
                    visited[curr] = True
                    
                    # Check all neighbors in the current row (adjacency matrix)
                    for neighbor, connected in enumerate(isConnected[curr]):
                        if connected and not visited[neighbor]:
                            stack.append(neighbor)

        province_count = 0
        
        # Iterate through each city to find unvisited components
        for i in range(n):
            if not visited[i]:
                province_count += 1
                dfs(i)
                
        return province_count

Edge Cases Handled

  • Single City (N=1N=1): The loop runs once, isConnected[0][0] is 1. DFS marks it as visited. Count becomes 1. Correct.
  • Fully Connected: All nodes are reachable from the first node processed. Loop finishes after one DFS call (or minimal calls). Returns 1. Correct.
  • No Connections (N>1N > 1): Each city is its own component. The loop increments count for every unvisited i. Returns NN. Correct.
  • Recursion Depth: Although recursion depth could theoretically hit limits, with N≤200N \le 200, the default Python stack limit (usually ~1000) handles this safely without needing an iterative stack implementation explicitly in production code for these constraints.