LeetCode 323: Number of Connected Components in an Undirected Graph Solution in Python – A Step-by-Step Guide

What Is LeetCode 323: Number of Connected Components in an Undirected Graph?

In LeetCode 323: Number of Connected Components in an Undirected Graph, you’re given an integer n (number of nodes, labeled 0 to n-1) and an array edges of undirected edge pairs. Your task is to return the number of connected components—disjoint subgraphs where every pair of nodes has a path. For example, with n = 5 and edges = [[0,1],[1,2],[3,4]], there are 2 components: {0,1,2} and {3,4}. This problem tests your ability to identify graph connectivity, linking to classics like LeetCode 200: Number of Islands.

Problem Statement

• Input: Integer n (nodes) and array edges (list of [u,v] pairs).
• Output: An integer—the number of connected components.
• Rules:
• Nodes are 0 to n-1.
• Edges are undirected (u-v means v-u too).
• Graph may be disconnected.

Constraints

• 1 <= n <= 2000
• 0 <= edges.length <= 5000
• 0 <= u, v < n, u != v
• No duplicate edges.

Examples

• Input: n = 5, edges = [[0,1],[1,2],[3,4]]
• Output: 2 (Components: {0,1,2}, {3,4})
• Input: n = 5, edges = [[0,1],[1,2],[2,3],[3,4]]
• Output: 1 (One component: {0,1,2,3,4})
• Input: n = 3, edges = []
• Output: 3 (Three isolated nodes)

Understanding the Problem: Counting Components

To solve LeetCode 323: Number of Connected Components in an Undirected Graph in Python, we need to count distinct groups of connected nodes in an undirected graph. A naive approach—checking every node pair for connectivity—is O(n²), too slow for large graphs. Instead, we’ll use:

• Best Solution (Union-Find): O(n + e * α(n)) time, O(n) space—fast and scalable (e = edges, α = inverse Ackermann).
• Alternative Solution (DFS): O(n + e) time, O(n + e) space—intuitive and explicit.

Let’s start with the Union-Find solution, explained in a beginner-friendly way.

Best Solution: Union-Find (Disjoint Set)

Why This Is the Best Solution

The Union-Find approach is the top choice for LeetCode 323 because it’s highly efficient—O(n + e * α(n)) time, O(n) space—and excels at tracking connectivity dynamically. It uses a disjoint-set data structure to merge components as edges are processed, counting how many remain. It’s like uniting islands with bridges and tallying the groups—smart and quick!

How It Works

Think of this as a community builder:

• Step 1: Initialize:
• Each node starts as its own component (parent = itself).
• Count = n.
• Step 2: Union Edges:
• For each edge, merge the components of its nodes.
• Decrease count if they were separate.
• Step 3: Find Roots:
• Use path compression for speed.
• Step 4: Why It Works:
• Merges track connectivity.
• Final count = number of components.

It’s like linking islands one bridge at a time!

Step-by-Step Example

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

• Init: Parent = [0,1,2,3,4], Count = 5
• Edge [0,1]: Union(0,1), Parent = [0,0,2,3,4], Count = 4
• Edge [1,2]: Union(1,2), Parent = [0,0,0,3,4], Count = 3
• Edge [3,4]: Union(3,4), Parent = [0,0,0,3,3], Count = 2
• Result: 2 components

Code with Detailed Line-by-Line Explanation

Copy codeclass Solution:
    def countComponents(self, n: int, edges: List[List[int]]) -> int:
        # Initialize parent array and count
        parent = list(range(n))
        count = n

        # Find with path compression
        def find(x):
            if parent[x] != x:
                parent[x] = find(parent[x])  # Compress path
            return parent[x]

        # Union two nodes
        def union(x, y):
            nonlocal count
            root_x = find(x)
            root_y = find(y)
            if root_x != root_y:
                parent[root_x] = root_y
                count -= 1

        # Process all edges
        for u, v in edges:
            union(u, v)

        return count

• Lines 3-4: Each node is its own parent, count starts at n.
• Lines 7-10: Find root with path compression.
• Lines 13-18: Union merges components, decrements count if new.
• Lines 21-22: Process edges with union.
• Time Complexity: O(n + e * α(n))—near-linear with inverse Ackermann.
• Space Complexity: O(n)—parent array.

This is like a graph-connector wizard—fast and sleek!

Alternative Solution: DFS (Depth-First Search)

Why an Alternative Approach?

The DFS approach—O(n + e) time, O(n + e) space—explores the graph explicitly, marking visited nodes to count components. It’s more intuitive for those familiar with graph traversal, though slightly less efficient due to adjacency list construction. It’s like exploring each island group—clear and hands-on!

How It Works

Explore connected nodes:

• Step 1: Build adjacency list from edges.
• Step 2: DFS from each unvisited node:
• Mark all reachable nodes in a component.
• Step 3: Count components as you go.

Step-by-Step Example

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

• Adj List: {0:[1], 1:[0], 2:[3], 3:[2]}
• DFS:
• Start 0: Visit 0, 1 → Component 1
• Start 2: Visit 2, 3 → Component 2
• Result: 2 components

Code for DFS Approach

Copy codefrom collections import defaultdict

class Solution:
    def countComponents(self, n: int, edges: List[List[int]]) -> int:
        # Build adjacency list
        graph = defaultdict(list)
        for u, v in edges:
            graph[u].append(v)
            graph[v].append(u)

        # DFS to mark connected component
        def dfs(node, visited):
            visited.add(node)
            for neighbor in graph[node]:
                if neighbor not in visited:
                    dfs(neighbor, visited)

        # Count components
        visited = set()
        components = 0
        for node in range(n):
            if node not in visited:
                dfs(node, visited)
                components += 1

        return components

• Time Complexity: O(n + e)—visit each node and edge once.
• Space Complexity: O(n + e)—adjacency list and visited set.

It’s a graph-exploring adventurer—vivid and direct!

Comparing the Two Solutions

• Union-Find (Best):
• Pros: O(n + e * α(n)) time, O(n) space, near-linear.
• Cons: Union-Find logic less visual.
• DFS (Alternative):
• Pros: O(n + e) time, O(n + e) space, intuitive traversal.
• Cons: More memory, slightly slower setup.

Union-Find wins for efficiency.

Additional Examples and Edge Cases

• n=3, []: 3 (Isolated nodes).
• n=2, [[0,1]]: 1.
• n=1, []: 1.

Both handle these perfectly.

Complexity Breakdown

• Union-Find: Time O(n + e * α(n)), Space O(n).
• DFS: Time O(n + e), Space O(n + e).

Union-Find is the leaner choice.

Key Takeaways

• Union-Find: Merge and count—brilliant!
• DFS: Explore and mark—clear!
• Python: Sets and lists shine—see [Python Basics](/python/basics).
• Graphs: Connectivity is key.

Final Thoughts: Map the Components

LeetCode 323: Number of Connected Components in an Undirected Graph in Python is a graph theory gem. Union-Find offers speed and elegance, while DFS provides a tangible exploration. Want more graph challenges? Try LeetCode 200: Number of Islands or LeetCode 547: Number of Provinces. Ready to count? Head to Solve LeetCode 323 on LeetCode (premium) and connect those nodes today!