NeetCode #592LC-547MediumGraphs
← Back to All Problems#592 · #547 · Number of Provinces(省份数量)
📌 Problem Statement & Constraints
There are
n cities, some connected. Given an n x n adjacency matrix isConnected, return the number of provinces (connected components). Constraints: 1 <= n <= 200.💡 Core Algorithmic Approaches
- Count connected components by scanning the cities and starting a traversal from each unvisited one.
- The adjacency matrix makes the neighbour lookup
isConnected[i][j]. - Union-find with a component counter is an equally good alternative.
- This is the same problem as counting connected components from an edge list.
💻 Benchmark Python3 Implementation
class Solution:
def findCircleNum(self, isConnected: List[List[int]]) -> int:
n = len(isConnected)
seen = [False] * n
def dfs(i: int) -> None:
seen[i] = True
for j in range(n):
if isConnected[i][j] and not seen[j]:
dfs(j)
count = 0
for i in range(n):
if not seen[i]:
count += 1 # a new province
dfs(i)
return count⚡ Complexity Deep Dive
⏱️ Time Complexity
O(n^2): the adjacency matrix is fully scanned.
💾 Space Complexity
O(n) for the visited array plus the recursion depth.
⚠️ Interview Pitfalls & Follow-ups
- Forgetting the
seencheck before recursing: nodes would be revisited indefinitely. - Counting inside the DFS: the count belongs to the outer scan.
- Using the matrix as undirected incorrectly: it is symmetric by construction.
- Building an adjacency list: unnecessary given the matrix form, though it would reduce the scan to O(V + E).
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.