NUHMAN.com

Introduction

LeetCode 323: Number of Connected Components in an Undirected Graph is a fundamental graph problem where you're asked to determine how many separate connected components exist in a graph.

This is a great test of your understanding of graph traversal techniques like DFS, BFS, and Union-Find (Disjoint Set Union).

Problem Statement

You have a graph of n nodes labeled from 0 to n - 1. You are given an integer n and a list of edges where each edge is a pair [u, v] indicating a connection between nodes u and v.

Return the number of connected components in the graph.

Example

python

Input: n = 5, edges = [[0,1],[1,2],[3,4]]
Output: 2

Input: n = 5, edges = [[0,1],[1,2],[2,3],[3,4]]
Output: 1

Step-by-Step Solution

We’ll cover two common approaches:

✅ Approach 1: Depth-First Search (DFS)

1. Build an adjacency list from the edge list.
2. Use a visited set to track visited nodes.
3. For each unvisited node, start a DFS traversal, marking all reachable nodes.
4. Count how many times you start a DFS → that's the number of connected components.

✅ Python Code – DFS

python

class Solution:
    def countComponents(self, n: int, edges: list[list[int]]) -> int:
        from collections import defaultdict

        graph = defaultdict(list)
        for u, v in edges:
            graph[u].append(v)
            graph[v].append(u)

        visited = set()

        def dfs(node):
            for neighbor in graph[node]:
                if neighbor not in visited:
                    visited.add(neighbor)
                    dfs(neighbor)

        components = 0
        for i in range(n):
            if i not in visited:
                visited.add(i)
                dfs(i)
                components += 1

        return components

✅ Approach 2: Union-Find (Disjoint Set Union)

Use the Union-Find data structure to dynamically group nodes:

1. Initially, each node is its own parent.
2. For every edge, perform a union operation.
3. Count how many unique roots (leaders) remain at the end.

✅ Python Code – Union-Find

python

class Solution:
    def countComponents(self, n: int, edges: list[list[int]]) -> int:
        parent = [i for i in range(n)]

        def find(x):
            if parent[x] != x:
                parent[x] = find(parent[x])  # Path compression
            return parent[x]

        def union(x, y):
            rootX = find(x)
            rootY = find(y)
            if rootX != rootY:
                parent[rootY] = rootX

        for u, v in edges:
            union(u, v)

        # Count distinct roots
        return len(set(find(i) for i in range(n)))

🔍 Dry Run Example (DFS)

Input: n = 5, edges = [[0,1],[1,2],[3,4]]

• Components:
• {0, 1, 2}
• {3, 4}
• Answer: 2

⏱️ Time and Space Complexity

ApproachTime ComplexitySpace ComplexityDFSO(n + e)O(n + e)Union-FindO(e * α(n))O(n)

Where e = number of edges, and α(n) is the inverse Ackermann function (very slow-growing).

🧠 Key Insights

• Use DFS or BFS when you want to explore the graph.
• Use Union-Find for a fast component counting solution.
• This problem is a typical building block for many graph theory problems.

✅ Conclusion

LeetCode 323 is a great introduction to working with connected components in graphs. It's also a good opportunity to practice both traversal and disjoint set union approaches. Mastering this problem gives you the tools to tackle more complex graph-based problems.