Prerequisites
Before attempting this problem, you should be comfortable with:
- Graph Representation (Adjacency Matrix) - Understanding how to represent connections between nodes in a 2D matrix
- Depth First Search (DFS) - Recursive traversal technique used to explore all reachable nodes from a starting point
- Breadth First Search (BFS) - Level-by-level traversal using a queue to explore connected nodes
- Union-Find (Disjoint Set Union) - Data structure for efficiently tracking and merging connected components
1. Depth First Search
Intuition
A province is a group of directly or indirectly connected cities. This is essentially finding the number of connected components in an undirected graph. We can use DFS to explore all cities reachable from a starting city, marking them as visited. Each time we start a new DFS from an unvisited city, we have found a new province.
Algorithm
- Create a
visitedarray of sizeninitialized tofalse. - Initialize province count
resto0. - For each city
ifrom0ton-1:- If city
iis not visited:- Increment
res(found a new province). - Run
dfsfrom cityito mark all connected cities as visited.
- Increment
- If city
- In the
dfs:- Mark the current node as visited.
- For each neighbor
neithat is connected and not visited, recursively calldfs.
- Return
res.
class Solution:
def findCircleNum(self, isConnected: List[List[int]]) -> int:
n = len(isConnected)
res = 0
visited = [False] * n
def dfs(node):
visited[node] = True
for nei in range(n):
if isConnected[node][nei] and not visited[nei]:
dfs(nei)
for i in range(n):
if not visited[i]:
dfs(i)
res += 1
return resTime & Space Complexity
- Time complexity:
- Space complexity:
2. Depth First Search (Modifying Input)
Intuition
Instead of using a separate visited array, we can use the diagonal of the adjacency matrix itself to track visited status. Since isConnected[i][i] is always 1 (a city is connected to itself), we can set it to 0 when we visit that city. This saves space but modifies the input.
Algorithm
- Initialize province count
resto0. - For each city
ifrom0ton-1:- If
isConnected[i][i]equals1(not yet visited):- Increment
res. - Run
dfsfrom cityi.
- Increment
- If
- In the
dfs:- Set
isConnected[node][node] = 0to mark as visited. - For each neighbor
neithat is connected and whose diagonal is still1, recursively calldfs.
- Set
- Return
res.
class Solution:
def findCircleNum(self, isConnected: List[List[int]]) -> int:
n = len(isConnected)
res = 0
def dfs(node):
isConnected[node][node] = 0
for nei in range(n):
if node != nei and isConnected[node][nei] and isConnected[nei][nei]:
dfs(nei)
for i in range(n):
if isConnected[i][i]:
dfs(i)
res += 1
return resTime & Space Complexity
- Time complexity:
- Space complexity: for recursion stack.
3. Breadth First Search
Intuition
BFS provides an alternative to DFS for exploring connected components. Instead of going deep first, we explore all neighbors at the current level before moving to the next. The logic remains the same: start from an unvisited city, explore all reachable cities using a queue, and count each new starting point as a separate province.
Algorithm
- Create a
visitedarray of sizeninitialized tofalse. - Initialize province count
resto0and create an empty queue. - For each city
ifrom0ton-1:- If city
iis not visited:- Increment
res. - Mark city
ias visited and add it to the queue. - While the queue is not empty:
- Dequeue a city
node. - For each neighbor
neithat is connected and not visited, mark it visited and enqueue it.
- Dequeue a city
- Increment
- If city
- Return
res.
class Solution:
def findCircleNum(self, isConnected: List[List[int]]) -> int:
n = len(isConnected)
visited = [False] * n
res = 0
q = deque()
for i in range(n):
if not visited[i]:
res += 1
visited[i] = True
q.append(i)
while q:
node = q.popleft()
for nei in range(n):
if isConnected[node][nei] and not visited[nei]:
visited[nei] = True
q.append(nei)
return resTime & Space Complexity
- Time complexity:
- Space complexity:
4. Disjoint Set Union
Intuition
The Union-Find (Disjoint Set Union) data structure is designed for efficiently managing connected components. We start with each city as its own component. As we process connections, we union the components of connected cities. The final number of distinct components equals the number of provinces. Path compression and union by size optimizations make this approach nearly O(1) per operation.
Algorithm
- Initialize a DSU with
ncomponents, where each city is its own parent. - For each pair of cities
(i, j)whereisConnected[i][j] == 1:- Call
union(i, j)to merge their components. - The
unionoperation decrements the component count if the cities were in different components.
- Call
- Return the final component count from the DSU.
class DSU:
def __init__(self, n):
self.Parent = list(range(n + 1))
self.Size = [1] * (n + 1)
self.components = n
def find(self, node):
if self.Parent[node] != node:
self.Parent[node] = self.find(self.Parent[node])
return self.Parent[node]
def union(self, u, v):
pu = self.find(u)
pv = self.find(v)
if pu == pv:
return False
self.components -= 1
if self.Size[pu] >= self.Size[pv]:
self.Size[pu] += self.Size[pv]
self.Parent[pv] = pu
else:
self.Size[pv] += self.Size[pu]
self.Parent[pu] = pv
return True
def numOfComps(self):
return self.components
class Solution:
def findCircleNum(self, isConnected: List[List[int]]) -> int:
n = len(isConnected)
dsu = DSU(n)
for i in range(n):
for j in range(n):
if isConnected[i][j]:
dsu.union(i, j)
return dsu.numOfComps()Time & Space Complexity
- Time complexity:
- Space complexity:
Common Pitfalls
Confusing Nodes with Edges
The adjacency matrix isConnected[i][j] represents whether city i and city j are directly connected. A common mistake is treating the matrix indices as edge indices rather than node indices. Remember that n is the number of cities, not the number of connections.
Forgetting to Mark Nodes as Visited
When performing DFS or BFS, failing to mark a node as visited before or immediately after processing it can lead to infinite loops or counting the same province multiple times. Always mark nodes as visited as soon as they are encountered.
Misunderstanding the Diagonal
The diagonal elements isConnected[i][i] are always 1 (a city is connected to itself). When modifying the input to track visited status, be careful to use the diagonal correctly. Do not confuse self-connections with actual inter-city connections.