Problem Description

You are given a graph with n nodes labeled from 0 to n-1. The graph is represented by an integer n (the number of nodes) and an array edges, where each element edges[i] = [ai, bi] indicates that there is an undirected edge connecting nodes ai and bi.

Your task is to find and return the total number of connected components in the graph.

A connected component is a group of nodes where there is a path between any two nodes in the group, and these nodes are not connected to any other nodes outside the group. In other words, it's a maximal set of nodes that are all reachable from each other through the edges.

For example, if you have 5 nodes (0, 1, 2, 3, 4) and edges [[0,1], [2,3]], there would be 3 connected components:

• Component 1: nodes {0, 1} (connected by an edge)
• Component 2: nodes {2, 3} (connected by an edge)
• Component 3: node {4} (isolated node with no edges)

The solution uses Depth-First Search (DFS) to traverse the graph. It builds an adjacency list from the edges, then visits each node. When it encounters an unvisited node, it performs DFS to mark all nodes in that connected component as visited, counting this as one component. The process continues until all nodes have been visited, and the total count of components is returned.

Flowchart Walkthrough

First, let's pin down the algorithm using the Flowchart. Here's a step-by-step walkthrough:

Is it a graph?

• Yes: The problem explicitly states we have a graph with n nodes and edges connecting them.

Is it a tree?

• No: The graph is not necessarily a tree. It can have multiple disconnected components, and there's no guarantee of a single connected structure without cycles.

Is the problem related to directed acyclic graphs?

• No: The edges are undirected (each edge [ai, bi] connects nodes bidirectionally), and we're not dealing with directed edges or topological ordering.

Is the problem related to shortest paths?

• No: We're not finding shortest paths between nodes. We're counting connected components.

Does the problem involve connectivity?

• Yes: The core of the problem is about connectivity - we need to identify groups of nodes that are connected to each other (connected components).

Disjoint Set Union

• While DSU could solve this problem, the solution uses DFS instead. Let's continue exploring the alternative path.

Does the problem have small constraints?

• The constraints can vary, but for connectivity problems, DFS is a standard approach regardless of size.

DFS/backtracking

• Yes: DFS is perfect for exploring connected components. We can start from an unvisited node and use DFS to mark all reachable nodes as visited, identifying one complete component.

Conclusion: The flowchart leads us to use DFS for this connectivity problem. DFS allows us to traverse each connected component completely, marking all nodes in that component as visited before moving to the next unvisited node, effectively counting the number of separate connected components in the graph.

Intuition

When we think about connected components, we can visualize the graph as several "islands" of nodes, where nodes within each island can reach each other through edges, but there's no way to travel between different islands.

The key insight is that if we start from any node and explore as far as possible through the edges, we'll discover all nodes in that particular component. Once we've visited all nodes in one component, we can move to any unvisited node - which must belong to a different component - and repeat the process.

This naturally leads us to a traversal approach. Starting from node 0, we can use DFS to "paint" all reachable nodes as visited. This gives us our first component. Then we look for the next unpainted node and repeat. Each time we start a new DFS from an unvisited node, we've found a new component.

Why DFS specifically? When we encounter a node, we want to immediately explore all its connections before moving on. DFS does exactly this - it goes as deep as possible along each path before backtracking. This ensures we fully explore one component before accidentally counting parts of it as separate components.

The algorithm becomes straightforward:

1. Build an adjacency list from the edges to make traversal efficient
2. Keep track of visited nodes to avoid counting the same component multiple times
3. For each unvisited node, launch a DFS that marks all reachable nodes as visited
4. Each successful DFS launch (returning 1 when starting from an unvisited node) represents discovering a new component

The beauty of this approach is that each node is visited exactly once, and we naturally partition the graph into its connected components through the traversal process.

Solution Approach

The implementation follows the DFS approach we identified through our analysis. Let's walk through the solution step by step:

1. Building the Adjacency List

First, we construct an adjacency list g where g[i] contains all neighbor nodes of node i:

g = [[] for _ in range(n)]
for a, b in edges:
    g[a].append(b)
    g[b].append(a)

Since the graph is undirected, we add both directions for each edge. This allows us to traverse from any node to its neighbors efficiently.

2. DFS Helper Function

The core of our solution is the DFS function:

def dfs(i: int) -> int:
    if i in vis:
        return 0
    vis.add(i)
    for j in g[i]:
        dfs(j)
    return 1

This function does two things:

• If node i is already visited, it returns 0 (no new component found)
• If node i is unvisited, it marks it as visited, recursively visits all its neighbors, and returns 1 (new component found)

The recursive calls to dfs(j) ensure we visit all nodes reachable from node i, effectively exploring the entire connected component.

3. Counting Components

The main logic uses a set vis to track visited nodes and counts components:

vis = set()
return sum(dfs(i) for i in range(n))

We iterate through all nodes from 0 to n-1. For each node:

• If it's already visited (part of a previously discovered component), dfs returns 0
• If it's unvisited (start of a new component), dfs returns 1 and marks all reachable nodes as visited

The sum() function accumulates these return values, giving us the total number of connected components.

Time and Space Complexity:

• Time: O(V + E) where V is the number of vertices and E is the number of edges. We visit each node once and traverse each edge twice (once from each direction).
• Space: O(V) for the adjacency list, visited set, and recursion stack in the worst case.

Example Walkthrough

Let's walk through a concrete example with 6 nodes (labeled 0-5) and edges [[0,1], [0,2], [3,4]].

Step 1: Build the adjacency list

Node 0: neighbors [1, 2]
Node 1: neighbors [0]
Node 2: neighbors [0]
Node 3: neighbors [4]
Node 4: neighbors [3]
Node 5: neighbors []

Step 2: Initialize visited set and component count

• vis = {} (empty set)
• We'll call dfs(i) for each node 0 through 5

Step 3: Process each node

Starting with node 0:

• Node 0 is not visited, so we mark it and explore
• Visit neighbor 1: mark as visited
• Visit neighbor 2: mark as visited
• dfs(0) returns 1 (found new component)
• vis = {0, 1, 2}

Node 1:

• Already in vis, so dfs(1) returns 0

Node 2:

• Already in vis, so dfs(2) returns 0

Node 3:

• Node 3 is not visited, so we mark it and explore
• Visit neighbor 4: mark as visited
• dfs(3) returns 1 (found new component)
• vis = {0, 1, 2, 3, 4}

Node 4:

• Already in vis, so dfs(4) returns 0

Node 5:

• Node 5 is not visited, so we mark it
• No neighbors to explore
• dfs(5) returns 1 (found new component)
• vis = {0, 1, 2, 3, 4, 5}

Step 4: Sum the results Total = 1 + 0 + 0 + 1 + 0 + 1 = 3 connected components

The three components are:

1. {0, 1, 2} - connected through edges
2. {3, 4} - connected through an edge
3. {5} - isolated node

Solution Implementation

Time and Space Complexity

Time Complexity: O(n + m)

The algorithm performs a depth-first search (DFS) to count connected components in an undirected graph. Breaking down the time complexity:

• Building the adjacency list: O(m) - iterates through all edges once
• DFS traversal: O(n + m) - each node is visited at most once (O(n)), and for each node, we explore all its edges (O(m) total across all nodes)
• The main loop calls dfs(i) for each node from 0 to n-1, but due to the visited set check, each node is actually processed only once

Therefore, the overall time complexity is O(n + m).

Space Complexity: O(n + m)

The space usage consists of:

• Adjacency list g: O(n + m) - n lists to store nodes, and 2m total edge entries (each undirected edge is stored twice)
• Visited set vis: O(n) - can contain at most n nodes
• Recursion call stack: O(n) in the worst case when the graph is a long path

The dominant factor is the adjacency list storage, giving us a total space complexity of O(n + m).

Common Pitfalls

1. Forgetting to Handle Isolated Nodes

A common mistake is assuming all nodes will appear in the edges array. Isolated nodes (nodes with no edges) won't appear in the edges list but still count as separate components.

Incorrect approach:

# Only iterating through nodes that appear in edges
nodes_in_edges = set()
for a, b in edges:
    nodes_in_edges.add(a)
    nodes_in_edges.add(b)
return sum(dfs(i) for i in nodes_in_edges)  # Misses isolated nodes!

Correct approach:

# Iterate through ALL nodes from 0 to n-1
return sum(dfs(i) for i in range(n))

2. Treating the Graph as Directed

Since the graph is undirected, each edge should be added in both directions in the adjacency list.

Incorrect approach:

# Only adding edge in one direction
for a, b in edges:
    adjacency_list[a].append(b)  # Missing the reverse direction!

Correct approach:

# Adding edge in both directions
for a, b in edges:
    adjacency_list[a].append(b)
    adjacency_list[b].append(a)

3. Stack Overflow with Large Components

For graphs with very deep components (like a long chain), recursive DFS can cause stack overflow. Python's default recursion limit is around 1000.

Solution using iterative DFS:

def dfs_iterative(start: int) -> int:
    if start in visited:
        return 0
  
    stack = [start]
    while stack:
        node = stack.pop()
        if node in visited:
            continue
        visited.add(node)
        for neighbor in adjacency_list[node]:
            if neighbor not in visited:
                stack.append(neighbor)
    return 1

4. Using Wrong Data Structure for Visited Tracking

Using a list instead of a set for tracking visited nodes leads to O(n) lookup time instead of O(1).

Inefficient approach:

visited = []  # O(n) lookup time
if node not in visited:  # This is O(n) operation
    visited.append(node)

Efficient approach:

visited = set()  # O(1) lookup time
if node not in visited:  # This is O(1) operation
    visited.add(node)