#547
Number of Provinces
Medium Connected components (adjacency matrix)
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
isConnected[i][j] = 1 means cities i and j are directly connected. A province is a group of connected cities. Count provinces.
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: how many connected groups of cities?
Why this works: the input is an adjacency matrix; count how many DFS runs you need to visit every city.
Example: [[1,1,0],[1,1,0],[0,0,1]]
DFS from 0 visits 0, 1DFS from 2 visits 2 → 2 provinces
✦Hints open one at a time
The input is an adjacency matrix.
Count how many times you have to start a new DFS.
↗Approach
For each unvisited city, increment the count and DFS through row i of the matrix to mark its whole component.
</>Solution (Java)
class Solution {
public int findCircleNum(int[][] isConnected) {
int n = isConnected.length, provinces = 0;
boolean[] seen = new boolean[n];
for (int i = 0; i < n; i++) {
if (!seen[i]) {
provinces++;
dfs(isConnected, i, seen);
}
}
return provinces;
}
private void dfs(int[][] g, int u, boolean[] seen) {
seen[u] = true;
for (int v = 0; v < g.length; v++) {
if (g[u][v] == 1 && !seen[v]) dfs(g, v, seen);
}
}
}!Common mistake
Treating the matrix as a grid and running "islands" over its cells — the cells are edges, not nodes.
Complexity
- Time: O(n²).
- Space: O(n).
Topic: Graphs
🎬 Episodes 74–85: video coming soon