Skip to content
Work Practice Products Coding interviews Machine learning coding Quant developer HFT course Blog Method Why me About Enquire Book a call

Coding · Graphs

The connected components pattern

Lesson · 9 min read · Graphs · Pattern: connected components

Split the graph into its separate pieces, compute something for each piece, then combine the results.

What the pattern is

Many problems ask for a number computed piece by piece. How many islands? How large is the largest? What is the cheapest node in each group, added up over all groups? Each one has the same shape: find every connected component, compute a value over the nodes of each one (call it f), and combine the components' values (call it g).

Components template

solve(graph)

  1. Set answer to the identity of g (0 for a count or sum, −∞ for a maximum).
  2. For each node s not yet visited: run a search from s, marking every node it reaches and accumulating f over them.
  3. Fold that component's value into answer with g.
  4. Return answer.
Questionf (per component)g (across components)
How many islands?1sum
Size of the largest island?count of cellsmax
Sum of the cheapest node in each group?min of valuessum
Can everyone reach everyone?1sum, then compare with 1

How to recognise it

  • "Groups", "islands", "regions", "provinces", "clusters", "friend circles", "accounts that belong together".
  • The answer is a number per group or an aggregate of such numbers, not a path or a distance.
  • The graph is undirected (or the relation is symmetric). For directed graphs the equivalent idea is the strongly connected component, a different algorithm.
  • Edges arriving over time with queries in between: use union-find instead of repeated searches.

Worked example: the cheapest node in each group

Eight nodes, each with a value (the tag above it). Find the groups and the smallest value in each, then add them up.

Each new search paints one component.

  1. Step 1 / 3
    0713293448566275
    groups1

    Node 0 is not in any group yet: start a search from it. It reaches 0, 1, 2: group 1, size 3, smallest value 3.

  2. Step 2 / 3
    0713293448566275
    groups2

    Node 3 is not in any group yet: start a search from it. It reaches 3, 4, 7: group 2, size 3, smallest value 4.

  3. Step 3 / 3
    0713293448566275
    groups3

    Node 5 is not in any group yet: start a search from it. It reaches 5, 6: group 3, size 2, smallest value 2. Every node belongs to a group: 3 in all.

Groups {0, 1, 2}, {3, 4, 7} and {5, 6} have minimums 3, 4 and 2, so the answer is 9.

TimeO(n + m)
SpaceO(n)

Every node is reached by exactly one search, and every edge is examined twice.

The problems in this module: