# LeetCode 323: Number of Connected Components in an Undirected Graph ## Problem Restatement We are given: ```python n edges ``` There are `n` nodes labeled: ```text 0 to n - 1 ``` `edges` describes an undirected graph. Return the number of connected components. A connected component is a maximal group of nodes where every node can reach every other node in the group. The official problem defines the graph as undirected with nodes labeled from `0` to `n - 1`. ([github.com](https://github.com/doocs/leetcode/blob/main/solution/0300-0399/0323.Number%20of%20Connected%20Components%20in%20an%20Undirected%20Graph/README_EN.md?utm_source=chatgpt.com)) ## Input and Output | Item | Meaning | |---|---| | Input | Number of nodes `n` and undirected edges | | Output | Number of connected components | | Graph type | Undirected | | Node labels | `0` through `n - 1` | Function shape: ```python def countComponents( n: int, edges: list[list[int]], ) -> int: ... ``` ## Examples Example 1: ```python n = 5 edges = [[0, 1], [1, 2], [3, 4]] ``` Graph: ```text 0 -- 1 -- 2 3 -- 4 ``` There are two connected groups: ```text {0,1,2} {3,4} ``` Output: ```python 2 ``` Example 2: ```python n = 5 edges = [[0,1], [1,2], [2,3], [3,4]] ``` Graph: ```text 0 -- 1 -- 2 -- 3 -- 4 ``` Every node is connected. Output: ```python 1 ``` ## First Thought: Explore Each Group If we start from one node and traverse all reachable nodes, we discover one complete connected component. Then: 1. Pick an unvisited node. 2. Run DFS or BFS. 3. Mark all reachable nodes. 4. Increase component count. 5. Repeat. This directly matches the definition of connected components. ## Graph Representation The graph is undirected. So for every edge: ```python [a, b] ``` we add: ```text a -> b b -> a ``` An adjacency list works well. Example: ```python edges = [[0,1], [1,2], [3,4]] ``` Adjacency list: | Node | Neighbors | |---:|---| | `0` | `[1]` | | `1` | `[0,2]` | | `2` | `[1]` | | `3` | `[4]` | | `4` | `[3]` | ## DFS Solution Maintain: ```python visited ``` When we see an unvisited node, run DFS from it. That DFS marks one whole connected component. So every DFS call corresponds to exactly one component. ## DFS Walkthrough Use: ```python n = 5 edges = [[0,1], [1,2], [3,4]] ``` Start: ```python visited = {} count = 0 ``` Node `0` is unvisited. Run DFS: ```text 0 -> 1 -> 2 ``` Now: ```python visited = {0,1,2} count = 1 ``` Node `3` is unvisited. Run DFS: ```text 3 -> 4 ``` Now: ```python visited = {0,1,2,3,4} count = 2 ``` All nodes are visited. Answer: ```python 2 ``` ## Algorithm 1. Build an adjacency list. 2. Create a visited set. 3. Initialize component count to `0`. 4. For each node: - If unvisited: - Run DFS or BFS. - Increment the component count. 5. Return the count. ## Correctness Whenever the algorithm starts DFS from an unvisited node `u`, the DFS visits every node reachable from `u`. Because the graph is undirected, every node in the same connected component as `u` is reachable from `u`, so the DFS marks the entire component. The DFS cannot visit nodes from another component, because no path exists between different connected components. Therefore: - One DFS call visits exactly one connected component. - Every connected component eventually triggers exactly one DFS call. The algorithm increments the counter once per DFS call, so the final count equals the number of connected components in the graph. ## Complexity Let: | Symbol | Meaning | |---|---| | `n` | Number of nodes | | `m` | Number of edges | | Metric | Value | Why | |---|---:|---| | Time | `O(n + m)` | Every node and edge is processed once | | Space | `O(n + m)` | Adjacency list and visited set | ## DFS Implementation ```python from collections import defaultdict class Solution: def countComponents( self, n: int, edges: list[list[int]], ) -> int: graph = defaultdict(list) for a, b in edges: graph[a].append(b) graph[b].append(a) visited = set() def dfs(node: int) -> None: visited.add(node) for neighbor in graph[node]: if neighbor not in visited: dfs(neighbor) components = 0 for node in range(n): if node not in visited: dfs(node) components += 1 return components ``` ## Code Explanation Build the adjacency list. ```python graph = defaultdict(list) ``` For every undirected edge: ```python graph[a].append(b) graph[b].append(a) ``` Track visited nodes. ```python visited = set() ``` DFS marks all reachable nodes. ```python def dfs(node: int) -> None: ``` Mark current node. ```python visited.add(node) ``` Then recursively visit neighbors. ```python for neighbor in graph[node]: if neighbor not in visited: dfs(neighbor) ``` Now scan all nodes. ```python for node in range(n): ``` If a node is unvisited, it starts a new component. ```python if node not in visited: ``` Run DFS and increase the count. ```python dfs(node) components += 1 ``` ## BFS Implementation The same logic also works with BFS. ```python from collections import defaultdict, deque class Solution: def countComponents( self, n: int, edges: list[list[int]], ) -> int: graph = defaultdict(list) for a, b in edges: graph[a].append(b) graph[b].append(a) visited = set() components = 0 for start in range(n): if start in visited: continue components += 1 queue = deque([start]) visited.add(start) while queue: node = queue.popleft() for neighbor in graph[node]: if neighbor not in visited: visited.add(neighbor) queue.append(neighbor) return components ``` ## Union-Find Solution This problem is also a classic Union-Find application. Initially every node is its own component. For every edge: ```python [a, b] ``` merge the components containing `a` and `b`. The remaining number of disjoint sets is the answer. ```python class UnionFind: def __init__(self, n: int): self.parent = list(range(n)) self.rank = [0] * n self.components = n def find(self, x: int) -> int: if self.parent[x] != x: self.parent[x] = self.find(self.parent[x]) return self.parent[x] def union(self, a: int, b: int) -> None: root_a = self.find(a) root_b = self.find(b) if root_a == root_b: return if self.rank[root_a] < self.rank[root_b]: root_a, root_b = root_b, root_a self.parent[root_b] = root_a if self.rank[root_a] == self.rank[root_b]: self.rank[root_a] += 1 self.components -= 1 class Solution: def countComponents( self, n: int, edges: list[list[int]], ) -> int: uf = UnionFind(n) for a, b in edges: uf.union(a, b) return uf.components ``` ## Testing ```python def run_tests(): s = Solution() assert s.countComponents( 5, [[0, 1], [1, 2], [3, 4]], ) == 2 assert s.countComponents( 5, [[0,1], [1,2], [2,3], [3,4]], ) == 1 assert s.countComponents( 4, [], ) == 4 assert s.countComponents( 1, [], ) == 1 assert s.countComponents( 6, [[0,1], [1,2], [3,4]], ) == 3 assert s.countComponents( 7, [[0,1], [1,2], [2,0], [3,4], [5,6]], ) == 3 print("all tests passed") run_tests() ``` Test meaning: | Test | Why | |---|---| | Two disconnected groups | Standard example | | Fully connected chain | Single component | | No edges | Every node isolated | | Single node | Smallest graph | | One isolated node plus groups | Mixed structure | | Graph with cycle | Confirms cycles do not affect counting |