Number of Provinces
Problem
Given an n x n matrix isConnected where isConnected[i][j] = 1 if the ith city and the jth city are directly connected, and 0 otherwise, return the total number of provinces (groups of directly or indirectly connected cities).
- 1 ≤ n ≤ 200
- isConnected.length == n
- isConnected[i].length == n
- isConnected[i][j] is 0 or 1
- isConnected[i][i] == 1
- isConnected[i][j] == isConnected[j][i]
Example
isConnected = [[1,1,0],[1,1,0],[0,0,1]]2The cities 0 and 1 are directly connected, forming one province. City 2 is isolated, forming a second province. The DFS starts at city 0, marks city 1 as visited through the connection, and completes the first province. Then it moves to city 2, which is unvisited, marking the second province. The total count is 2.
Approach
Straightforward Solution
A brute-force approach would check every pair of cities and attempt to group them, but without efficient traversal, this leads to redundant checks and higher complexity.
Core Observation
The problem reduces to counting connected components in an undirected graph represented by an adjacency matrix. Each city is a node, and edges exist where isConnected[i][j] == 1.
Path to Optimal
Recognizing the problem as connected components counting suggests graph traversal algorithms. DFS or BFS can explore all nodes reachable from a starting node, marking them visited. Each unvisited node found during iteration indicates a new province. This approach ensures each city is visited exactly once, avoiding redundant work.
Optimal Approach
Iterate over each city. If it is unvisited, increment the province count and perform a DFS to mark all cities connected to it as visited. The DFS recursively visits all neighbors connected directly or indirectly. After processing all cities, the province count reflects the number of connected components.
Time
O(n^2)
The adjacency matrix has n^2 entries. The DFS explores each node and its neighbors once, resulting in O(n^2) time since each edge is checked via the matrix.
Space
O(n)
The auxiliary space is O(n) for the recursion stack in the worst case and the visited set storing up to n nodes.
Pattern Spotlight
DFS (Connected Components in Graph)
When counting groups of connected nodes in an undirected graph, use DFS to explore and mark all nodes in a component starting from any unvisited node, incrementing the count each time a new unvisited node is found.
Solution
| 1 | class Solution:
|
| 2 | def findCircleNum(self, isConnected: List[List[int]]) -> int:
|
| 3 | n = len(isConnected)
|
| 4 | seen = set()
|
| 5 |
|
| 6 | def dfs(i):
|
| 7 | for j in range(n):
|
| 8 | if isConnected[i][j] == 1 and j not in seen:
|
| 9 | seen.add(j)
|
| 10 | dfs(j)
|
| 11 |
|
| 12 | provinces = 0
|
| 13 | for i in range(n):
|
| 14 | if i not in seen:
|
| 15 | provinces += 1
|
| 16 | seen.add(i)
|
| 17 | dfs(i)
|
| 18 |
|
| 19 | return provinces |
| 1 | import java.util.HashSet; |
| 2 | import java.util.Set; |
| 3 | |
| 4 | public class Solution { |
| 5 | public int findCircleNum(int[][] isConnected) { |
| 6 | int n = isConnected.length; |
| 7 | Set<Integer> seen = new HashSet<>(); |
| 8 | |
| 9 | // DFS helper function |
| 10 | class DFS { |
| 11 | void dfs(int i) { |
| 12 | for (int j = 0; j < n; j++) { |
| 13 | if (isConnected[i][j] == 1 && !seen.contains(j)) { |
| 14 | seen.add(j); |
| 15 | dfs(j); |
| 16 | } |
| 17 | } |
| 18 | } |
| 19 | } |
| 20 | |
| 21 | DFS dfsHelper = new DFS(); |
| 22 | int provinces = 0; |
| 23 | for (int i = 0; i < n; i++) { |
| 24 | if (!seen.contains(i)) { |
| 25 | provinces++; |
| 26 | seen.add(i); |
| 27 | dfsHelper.dfs(i); |
| 28 | } |
| 29 | } |
| 30 | |
| 31 | return provinces; |
| 32 | } |
| 33 | } |
| 1 | #include <vector> |
| 2 | #include <unordered_set> |
| 3 | |
| 4 | using namespace std; |
| 5 | |
| 6 | class Solution { |
| 7 | public: |
| 8 | int findCircleNum(vector<vector<int>>& isConnected) { |
| 9 | int n = isConnected.size(); |
| 10 | unordered_set<int> seen; |
| 11 | |
| 12 | function<void(int)> dfs = [&](int i) { |
| 13 | for (int j = 0; j < n; ++j) { |
| 14 | if (isConnected[i][j] == 1 && seen.find(j) == seen.end()) { |
| 15 | seen.insert(j); |
| 16 | dfs(j); |
| 17 | } |
| 18 | } |
| 19 | }; |
| 20 | |
| 21 | int provinces = 0; |
| 22 | for (int i = 0; i < n; ++i) { |
| 23 | if (seen.find(i) == seen.end()) { |
| 24 | provinces++; |
| 25 | seen.insert(i); |
| 26 | dfs(i); |
| 27 | } |
| 28 | } |
| 29 | |
| 30 | return provinces; |
| 31 | } |
| 32 | }; |
| 1 | var findCircleNum = function(isConnected) { |
| 2 | const n = isConnected.length; |
| 3 | const seen = new Set(); |
| 4 | |
| 5 | function dfs(i) { |
| 6 | for (let j = 0; j < n; j++) { |
| 7 | if (isConnected[i][j] === 1 && !seen.has(j)) { |
| 8 | seen.add(j); |
| 9 | dfs(j); |
| 10 | } |
| 11 | } |
| 12 | } |
| 13 | |
| 14 | let provinces = 0; |
| 15 | for (let i = 0; i < n; i++) { |
| 16 | if (!seen.has(i)) { |
| 17 | provinces++; |
| 18 | seen.add(i); |
| 19 | dfs(i); |
| 20 | } |
| 21 | } |
| 22 | |
| 23 | return provinces; |
| 24 | }; |
Step-by-Step Solution
Initialize Variables and Define DFS Traversal
| 3 | n = len(isConnected)
|
| 4 | seen = set()
|
| 6 | def dfs(i):
|
| 7 | for j in range(n):
|
| 8 | if isConnected[i][j] == 1 and j not in seen:
|
| 9 | seen.add(j)
|
| 10 | dfs(j)
|
Objective
To prepare the data structures needed for traversal and define the recursive DFS function to explore connected cities.
Key Insight
Storing visited cities in a set prevents revisiting and infinite loops. The DFS function systematically explores all neighbors of a city, recursively marking connected cities as visited. This encapsulates the core traversal logic, enabling efficient connected component detection.
Interview Quick-Check
Core Logic
The DFS function recursively visits all cities connected to the current city, marking them visited to avoid repeated processing.
State & Boundaries
The visited set tracks which cities have been explored, ensuring each city is processed once.
Common Pitfalls & Bugs
Forgetting to add a city to the visited set before recursive DFS calls can cause infinite recursion or repeated visits.
Count Provinces by Iterating Over Cities and Invoking DFS
| 12 | provinces = 0
|
| 13 | for i in range(n):
|
| 14 | if i not in seen:
|
| 15 | provinces += 1
|
| 16 | seen.add(i)
|
| 17 | dfs(i)
|
Objective
To iterate through all cities, identify unvisited ones, increment the province count, and trigger DFS to mark all connected cities.
Key Insight
Each unvisited city represents a new province. By invoking DFS from that city, all cities in the same province are marked visited, preventing double counting. This approach ensures a linear pass over all cities with efficient grouping.
Interview Quick-Check
Core Logic
Increment the province count only when encountering an unvisited city, then mark its entire connected component via DFS.
State & Boundaries
The loop covers all cities, ensuring no province is missed.
Common Pitfalls & Bugs
Failing to add the starting city to the visited set before DFS can cause revisiting and incorrect province counts.
Return the Total Number of Provinces
| 19 | return provinces |
Objective
To output the final count of provinces after all cities have been processed.
Key Insight
After all DFS traversals, the provinces variable accurately reflects the number of connected components in the graph, which is the problem's required output.
Interview Quick-Check
Core Logic
Returning the province count completes the solution, representing the total connected components found.
Line Analysis
This solution has 3 Critical lines interviewers watch for.
if isConnected[i][j] == 1 and j not in seen:Check if the neighbor city is connected and unvisited.
This conditional is critical because it ensures the DFS only explores valid, unvisited neighbors, preventing cycles and redundant traversals.
seen.add(j)Mark the neighbor city as visited.
Marking a city as visited before recursive calls is essential to avoid revisiting the same city multiple times, which would cause infinite recursion or incorrect province counts.
seen.add(i)Mark the current city as visited before DFS.
Adding the city to visited before DFS is critical to avoid infinite recursion and to correctly identify the province's extent.
seen = set()Initialize a set to track visited cities.
The visited set prevents revisiting cities, avoiding infinite recursion and redundant work during DFS traversal.
dfs(j)Recursively perform DFS on the neighbor city.
This recursive call explores all cities connected to the neighbor, extending the traversal to the entire connected component.
if i not in seen:Check if the current city has not been visited.
An unvisited city indicates a new province, triggering a DFS to mark all connected cities.
dfs(i)Invoke DFS to mark all cities connected to the current city.
This call explores the entire connected component, marking all cities in the province as visited.
def dfs(i):Define the recursive DFS function to explore connected cities.
Encapsulating the traversal logic in a recursive function allows systematic exploration of all cities connected to a given city, marking them visited.
provinces += 1Increment the province count for a new connected component.
Each unvisited city found corresponds to a distinct province, so the count must increase.
return provincesReturn the total number of provinces found.
After all cities are processed, this value correctly represents the number of connected components in the graph.
for j in range(n):Iterate over all possible neighboring cities.
Checking all cities ensures that all direct connections from the current city are considered for traversal.
for i in range(n):Iterate over each city to identify unvisited provinces.
This loop ensures every city is checked, guaranteeing all provinces are counted.
n = len(isConnected)Calculate the number of cities from the adjacency matrix size.
Knowing the number of cities (nodes) is essential for iterating over all cities and indexing the adjacency matrix correctly.
provinces = 0Initialize the province count to zero.
This variable accumulates the total number of connected components found during iteration.
Test Your Understanding
Why does performing a DFS from each unvisited city correctly count the number of provinces?
Because each DFS call explores all cities connected directly or indirectly to the starting city, marking them visited. Thus, each DFS corresponds to exactly one connected component (province), and counting these calls yields the total number of provinces.
Related Problems
DFS pattern
Don't just read it. Drill it.
Reconstruct Number of Provinces from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.
Unlock the Number of Provinces drill