LeetCode Solutions Blog

Number of Connected Components in an Undirected Graph

Number: 323

Difficulty: Medium

Paid? Yes

Problem Description

Given an undirected graph with n nodes and an array of edges, determine the number of connected components in the graph.

Key Insights

Use an adjacency list to represent the graph.
A DFS (or BFS) traversal from an unvisited node will traverse an entire connected component.
Each new DFS/BFS call from an unvisited node signals a separate connected component.
Alternatively, the Union-Find data structure can be used to union connected nodes and count distinct sets.

Space and Time Complexity

Time Complexity: O(n + e), where n is the number of nodes and e is the number of edges. Space Complexity: O(n + e) due to the storage of the graph and tracking of visited nodes.

Solution

We solve the problem by iterating over each node and performing a DFS for any node that hasn't been visited. The DFS uses an iterative approach with a stack to traverse all nodes in a connected component. Each DFS initiation corresponds to one connected component. This method efficiently explores the graph using an adjacency list and marks nodes as visited to prevent redundant traversals.

Code Solutions

# Function to count the number of connected components in an undirected graph.
def count_components(n, edges):
    # Build the adjacency list for the graph.
    graph = {i: [] for i in range(n)}
    for a, b in edges:
        graph[a].append(b)
        graph[b].append(a)
    
    # Set to keep track of visited nodes.
    visited = set()
    
    # Helper function to perform DFS traversal starting from a node.
    def dfs(node):
        stack = [node]
        while stack:
            current = stack.pop()
            if current not in visited:
                visited.add(current)
                for neighbor in graph[current]:
                    if neighbor not in visited:
                        stack.append(neighbor)

    # Count connected components by initiating DFS on unvisited nodes.
    count = 0
    for i in range(n):
        if i not in visited:
            dfs(i)
            count += 1
    return count

# Example usage:
print(count_components(5, [[0,1],[1,2],[3,4]]))  # Expected output: 2