Connected Components

🧠 Mental Model

This is your first "composite" algorithm: you're not learning something new, you're orchestrating Day 2/3 traversals with an outer loop. Recognizing that "count the groups" = "count traversal restarts" is a mental unlock that pays off through the rest of the course.

⚙️ Mechanics

1. Keep a global visited set and a count = 0.
2. Loop over every node. If it's unvisited: increment count, then BFS/DFS from it (marking everything reachable).
3. When the outer loop ends, count is the number of components.

Three flavors you'll meet

• Count components — just the outer-loop restart count.
• Label each node — assign each traversal a component id; store compId[node]. Enables O(1) "same component?" queries.
• Flood fill — the grid version: repaint a region, or process cells belonging to one region (islands are literally connected components).

📊 Complexity

Note the outer loop does not add a factor — a node visited in an earlier component is skipped, so total work stays linear. Union-Find (Week 2) solves the same problem incrementally and is preferred when edges arrive one at a time.

💻 Reference Implementation (Java)

Count components on an adjacency list, and label each node with its component id.

import java.util.*;

/** Returns number of connected components; fills compId[] with labels. */
public int countComponents(int n, List<Integer>[] adj, int[] compId) {
    boolean[] seen = new boolean[n];
    int components = 0;

    for (int start = 0; start < n; start++) {
        if (seen[start]) continue;          // already part of a counted component
        components++;                        // a NEW component begins here
        dfs(start, adj, seen, compId, components - 1);
    }
    return components;
}

private void dfs(int u, List<Integer>[] adj,
                 boolean[] seen, int[] compId, int id) {
    seen[u] = true;
    compId[u] = id;                          // label this node
    for (int v : adj[u])
        if (!seen[v]) dfs(v, adj, seen, compId, id);
}

// Now compId[a] == compId[b]  ⇔  a and b are in the same component (O(1) query)

⚠️ Common Pitfalls

🎯 Problems