Chapter 70

Home

Connected Components

A connected component is a set of nodes where every node is reachable from every other node. In an undirected graph, DFS from each unvisited node finds one component. Count them or label them.

Component Labelling with DFS

C++ — count and label components

vector comp(V, -1);
int comp_id = 0;

void dfs(int u, int id) {
    comp[u] = id;
    for (int v : adj[u])
        if (comp[v] == -1) dfs(v, id);
}

for (int i = 0; i < V; i++)
    if (comp[i] == -1) dfs(i, comp_id++);

// comp_id = number of connected components

Rust

fn dfs(u: usize, id: usize, adj: &[Vec], comp: &mut Vec) {
    comp[u] = id as i32;
    for &v in &adj[u] {
        if comp[v] == -1 { dfs(v, id, adj, comp); }
    }
}

let mut comp = vec![-1; V];
let mut comp_id = 0;
for i in 0..V {
    if comp[i] == -1 { dfs(i, comp_id, &adj, &mut comp); comp_id += 1; }
}

💡 Component size

Track component sizes with a vector<int> size(comp_id, 0) — increment size[id]++ during DFS. Useful for problems like "find the largest component."

Key Takeaways