Connected Components in Graphs

1. What are Connected Components?

An undirected graph is made up of one or more connected components. A connected component is a subgraph where there is a path between any two nodes within that component, but no path to any node outside of it.

Think of it like a social network. If you can trace a path of friendships from person A to person B, they are in the same component. If there's no possible chain of friends connecting person A to person C, then A and C are in different components.

Our task is to write an algorithm that counts how many of these separate "islands" exist in a given graph.

2. The Core Algorithm: Traversal with a Master Loop

In our previous lessons, we often started a DFS or BFS from a single source node (e.g., node 0). But what happens if the graph is disconnected, like the one above? A single traversal starting from node 1 would only visit nodes {1, 2, 3, 4}. It would never reach nodes {5, 6, 7, 8}.

So, how do we ensure we visit every node and count every component? The solution is beautifully simple and builds on what we already know.

To understand the high-level strategy, let's watch a short conceptual explanation.

As the video explained, the master algorithm is:

1. Initialize a component_count to 0.
2. Create a visited set to keep track of nodes we've already seen.
3. Loop through every node from 0 to n-1.
4. For each node, if it has not been visited yet:
   • We have found a new component! Increment component_count.
   • Start a traversal (like DFS or BFS) from this node. This traversal will find and mark all nodes in the current component as visited.
5. After the loop finishes, component_count will hold the total number of connected components.

3. Algorithm Walkthrough with DFS

Now, let's see this algorithm in action using DFS as our traversal method. The following video provides a step-by-step walkthrough of a concrete example.

To solidify your understanding, let's turn to a well-structured written explanation that breaks down the intuition and implementation steps.

4. Python Implementation

Now let's put all the pieces together into a single Python function. The implementation below is based on the approach from the Algo.monster resource, which is clean and efficient.

from collections import defaultdict

def count_components(n: int, edges: list[list[int]]) -> int:
    """
    Counts the number of connected components in an undirected graph.

    Args:
        n: The total number of nodes, labeled 0 to n-1.
        edges: A list of pairs representing undirected edges.

    Returns:
        The number of connected components.
    """
    # Step 1: Build the adjacency list representation of the graph.
    # We use a defaultdict to easily append to lists.
    adj = defaultdict(list)
    for u, v in edges:
        adj[u].append(v)
        adj[v].append(u)

    # Step 2: Initialize a set to track all visited nodes across all components.
    visited = set()
    component_count = 0

    def dfs(node: int):
        """A simple DFS to find all nodes in a component."""
        visited.add(node)
        for neighbor in adj[node]:
            if neighbor not in visited:
                dfs(neighbor)

    # Step 3: The master loop. Iterate through every possible node.
    for i in range(n):
        # If the node hasn't been visited, it's the start of a new component.
        if i not in visited:
            component_count += 1
            # Start DFS to find all nodes in this new component.
            dfs(i)
    
    return component_count

# --- Example Usage ---
# Graph 1: Two components {0, 1, 2} and {3, 4}
n1 = 5
edges1 = [[0, 1], [1, 2], [3, 4]]
print(f"Graph 1 has {count_components(n1, edges1)} components.") # Expected: 2

# Graph 2: One component {0, 1, 2, 3} and one isolated node {4}
# Note that node 4 is a component by itself.
n2 = 5
edges2 = [[0, 1], [1, 2], [2, 3]]
print(f"Graph 2 has {count_components(n2, edges2)} components.") # Expected: 2

5. Complexity and Competitive Programming Pitfalls

Understanding the performance and common mistakes is crucial for competitive programming.

Complexity Analysis

• Time Complexity: $O(V+E)$, where $V$ is the number of nodes (n) and $E$ is the number of edges.

  • Building the adjacency list takes $O(E)$ time.
  • The master loop runs $V$ times. The DFS function is called once for each component. Across all calls, each node and edge is visited exactly once. Therefore, the total time for all traversals is $O(V+E)$.
  • The overall complexity is dominated by these two parts, giving us $O(V+E)$.

• Space Complexity: $O(V+E)$

  • The adjacency list stores $2E$ entries in total for an undirected graph, so it takes $O(E)$ space. If we consider isolated nodes, the list itself takes $O(V)$ space. Thus, $O(V+E)$.
  • The visited set can store up to $V$ nodes, taking $O(V)$ space.
  • The recursion stack for DFS can go as deep as $V$ in the worst case (a long chain), taking $O(V)$ space.
  • The total space is therefore $O(V+E)$.

Common Pitfalls

It's easy to make small mistakes when implementing this. Let's review some common traps to avoid.

Conclusion

Congratulations! You've successfully learned how to find and count the connected components of an undirected graph. This pattern of combining a master loop with a graph traversal is a powerful tool in your competitive programming arsenal.

Key Takeaways:

• A connected component is a maximal set of nodes where every node is reachable from every other node in that set.
• For graphs that might be disconnected, a single traversal from one source is not enough.
• The standard algorithm is to iterate through all nodes from 0 to n-1. If a node hasn't been visited, you've found a new component, so you increment a counter and start a traversal (DFS or BFS) to mark all nodes within it.
• The time and space complexity of this approach is $O(V+E)$.

Up Next:
We've applied our traversal skills to cycle detection and finding connected components. In the next lesson, we will move to another important graph algorithm: Topological Sorting. This is used for ordering tasks or events that have dependencies, and it applies specifically to Directed Acyclic Graphs (DAGs).