⚡Flashcard Drill➔
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

  1. Count connected components by scanning the cities and starting a traversal from each unvisited one.
  2. The adjacency matrix makes the neighbour lookup isConnected[i][j].
  3. Union-find with a component counter is an equally good alternative.
  4. 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 seen check 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.
🎯 Drill This Card Now➔

🧩 Related Graphs Problems