Recipe

Find all SCCs of a small digraph by hand

Use when: you can see every arc in a small digraph directly and need to group vertices by mutual reachability, without running Tarjan's or Kosaraju's algorithm

Goal: the complete partition of the digraph's vertices into maximal mutually reachable groups

Taught in Strongly connected components

1. 1

   Follow arcs forward from each vertex and look for a path that returns to that same vertex. Every vertex on that closed loop can reach every other vertex on the same loop.

   Example

   On a digraph with arcs p\to q, q\to r, r\to p, r\to s, s\to t, t\to s, and u\to p: tracing from p gives p\to q\to r\to p, a closed cycle, so candidate \{p,q,r\}. Tracing from s gives s\to t\to s, another closed cycle, so candidate \{s,t\}.

   ⚡ Shortcut

   If no starting vertex ever leads back to itself, the digraph has no cycles at all (a DAG), and every vertex is already its own singleton SCC. Skip straight to Step 4's final list.

   Why: two vertices on one directed cycle can each reach the other by walking around the cycle, satisfying mutual reachability immediately.

2. 2

   Any vertex that never showed up on a traced cycle becomes a candidate component by itself.

   Example

   Vertex u only sends an arc out (u\to p) and never sits on a cycle. So \{u\} starts as its own candidate, separate from \{p,q,r\} and \{s,t\}.

   Why: reflexivity alone makes a lone vertex mutually reachable with itself, and only Step 3's check can merge it with anything else.

3. 3

   For each pair of candidate groups, check whether some arc sequence runs from one into the other. Then check separately whether an arc sequence runs back the other way.

   Example

   Arc r\to s sends \{p,q,r\} into \{s,t\}. But tracing every out-arc from s and t (s\to t, t\to s) never reaches back to p, q, or r. Only one direction holds, so the two groups stay separate.

   • both directions hold — merge the two candidates into one component.
   • only one direction holds, or neither — keep the two candidates separate.

   Why: an SCC needs mutual reachability, so a bridge running only one way links two components without merging them into one.

4. 4

   Once no pair of candidates merges any further, the current groups are the digraph's strongly connected components.

   Example

   Checking \{u\} against the other two groups: u\to p reaches both of them, but nothing ever arcs back to u. So \{u\} stays alone, giving final SCCs \{p,q,r\}, \{s,t\}, and \{u\}.

   Why: Step 3's merge test was applied to every pair, so once it stops firing, each remaining group is maximal.