323. Number of Connected Components in an Undirected Graph
Model: qwen3.5:9b
Topics: Depth-first Search,Breadth-first Search,Union Find,Graph
FAANG asked: 1
Acceptance rate: 58.2%
Problem Breakdown
We are given an undirected graph with labeled vertices ( to ) and a list of edges connecting them. The goal is to determine how many disjoint sets (connected components) exist in the entire structure.
Key Inputs:
n: Total number of nodes.edges: List of pairs[u, v]representing undirected connections.
Implicit Constraints & Edge Cases:
- Isolated Nodes: A node might not appear in any edge list (e.g., , edges only connect and ). This node () forms its own component. Our logic must account for nodes that never get merged into a larger set.
- Empty Edges: If
edgesis empty or , every node is isolated; the answer should be . - Disconnected Graphs: The graph might not form a single tree but multiple disjoint subgraphs (like Example 1).
Intuition
Initially, we can assume that without any edges provided in edges, every node exists as its own separate component. Therefore, the starting count of connected components is .
As we iterate through each edge [u, v]:
- If nodes
uandvare already part of the same connected group (i.e., they share a root in our data structure), adding this edge doesn’t change the number of components. We simply ignore it because redundancy is allowed but unnecessary for connectivity counting. - If
uandvbelong to different groups, connecting them merges these two distinct sets into one single component. This operation reduces the total count of connected components by exactly 1.
This logic suggests we need a data structure that efficiently tracks which nodes are in the same group and allows us to merge those groups quickly. A Disjoint Set Union (DSU) or Union-Find structure is ideal for this because it supports find (check if two elements share a root) and union (merge sets) operations nearly instantly ().
Alternatively, we could build an adjacency list and run BFS/DFS from every unvisited node. While valid, DSU avoids the overhead of building explicit graph structures when only connectivity counts are needed. I will proceed with Union-Find for its efficiency in this specific counting problem.
Approach
- Initialize: Create a
parentarray where each index points to itself (parent[i] = i). This represents initial components. Initialize a variablenum_componentsto . - Iterate Edges: Loop through every
[u, v]in the input list. - Find Roots: For both nodes
uandv, find their representative root using path compression (to keep tree height low). - Union Logic:
- If
root_u != root_v: Perform a union operation (make one parent point to the other, optionally by rank/size for balance) and decrementnum_components. - If
root_u == root_v: They are already connected; do nothing.
- If
- Return: After processing all edges, return
num_components.
Complexity Analysis
- Time Complexity: , where is the number of edges and is the inverse Ackermann function (effectively constant). Initialization takes . In practice, this simplifies to nearly linear time relative to input size.
- Space Complexity: for storing the
parentarray (and optionally arankorsizearray if used for union optimization).
Solution
class UnionFind:
def __init__(self, n):
self.parent = list(range(n))
# Optional rank/size arrays could be added here to ensure O(log N) height.
# For this problem constraints (N <= 2000), simple path compression is sufficient.
class Solution:
def countComponents(self, n: int, edges: List[List[int]]) -> int:
uf = UnionFind(n)
for u, v in edges:
root_u = self._find(uf.parent, u)
root_v = self._find(uf.parent, v)
if root_u != root_v:
# Merge the two sets.
# We attach one tree to another arbitrarily here (path compression handles balance).
uf.parent[root_u] = root_v
return n - len(edges) # Wait, this logic is flawed in thought process above?
# No, decrementing a counter inside loop is safer than math at end.
def _find(self, parent, x):
path_compression:
if parent[x] != x:
parent[x] = self._find(parent, parent[x])
return parent[x]
Correction on Code Logic: The previous snippet had a logic error in the thought block. I need to write clean code that decrements count or returns initial minus successful unions.
Revised Solution Plan:
Initialize count = n. Inside loop, if roots differ: union and decrement count. Return count.
I will implement iterative find for robustness against recursion limits in Python (default 1000), though path compression usually mitigates depth issues quickly enough. I’ll stick to recursive with memoization logic or just standard implementation which is accepted on LeetCode for N=2000. To be safe and “Senior”, I will use iterative find inside the solution block to avoid RecursionError risks entirely, even if unlikely here.
class Solution:
def countComponents(self, n: int, edges: List[List[int]]) -> int:
parent = list(range(n))
# Iterative Find with Path Compression
def find(i):
root = i
while root != parent[root]:
root = parent[root]
# Compress path from current node to root
curr = i
while curr != root:
nxt = parent[curr]
parent[curr] = root
curr = nxt
return root
components = n
for u, v in edges:
root_u = find(u)
root_v = find(v)
if root_u != root_v:
# Union by attaching one to another arbitrarily
parent[root_u] = root_v
components -= 1
return components
Edge Cases Handled
- Isolated Nodes: If a node never appears in
edges, its parent remains itself. It is counted as an initial component and never merged, correctly contributing to the final count. - Empty Edges List: The loop over edges does not execute; function returns initialized
n(correct). - Single Node (): Returns 1 regardless of edge list content (though constraints say , so valid indices exist).