Strongly Connected Components

Worked example: three groups, one-way connections

This original six-vertex example uses seven arrows: 0→1, 1→2, 2→0, 2→3, 3→4, 4→3 and 4→5. The first three vertices form a cycle, vertices 3 and 4 can return to each other, and vertex 5 has no outgoing arrow. Enumerating reachability gives the following maximal classes.

There are three SCCs and the largest has three vertices. Only 2→3 and 4→5 cross between classes, so the condensation is C0→C1→C2 with two arrows. The shortest 0-to-5 route is 0→1→2→3→4→5. There is no 5-to-0 route: reaching a downstream component once does not merge the groups.

A single arrow changes the partition

Add 5→0. Every vertex can now follow the cycle through all six vertices and return, giving one SCC, largest size six and zero condensation arrows. Instead, remove 2→0 from the original example: 0, 1 and 2 become separate singleton classes, leaving five SCCs in total and a four-arrow condensation chain.

Trace the two searches

With roots and neighbors examined in ascending order, the first DFS follows 0, 1, 2, 3, 4, 5. Vertices finish in the opposite order: 5, 4, 3, 2, 1, 0. Search the transpose with roots considered as 0, 1, 2, 3, 4, 5. The first new tree reaches 0, 2, 1; the next reaches 3, 4; the last contains 5. These trees recover exactly the reachability classes calculated above.

Experiment with the native controls

Open the interactive Strongly Connected Components module. The graph and final partition are available immediately; the replay separately exposes the algorithm's intermediate stack and discovered trees.

1. Choose Cycle chain under Graph example. Confirm three SCCs, seven unique arrows and two condensation arrows. With From vertex 0 and To vertex 5, read a forward path and no reverse path.
2. Choose Condensation DAG under Graph view. The native graph contracts to C0, C1 and C2. Change to Transpose graph: every original arrow reverses, but the final partition remains unchanged. The query cards continue to describe original G.
3. Return to Original graph and press Next step. The active white ring moves to vertex 0. Use Play scan, pause, or Finish scan to inspect the exit list and the three second-pass trees. Rewind scan returns the cursor to zero without changing the graph.
4. Append a new line 5 0 in Directed edges. Watch the six vertices acquire one component color, read SCC count one and see the return path 5→0. The edited graph starts a fresh replay.
5. Press Reset example, then append 0 3 and 1 4 on separate lines. There are nine unique original arrows, but still two condensation arrows: three different arrows from C0 to C1 collapse to one.
6. Drag a node to rearrange it and drag the background to pan. Reset view or Home restores the camera; Reset layout also restores automatic node positions. Neither changes the graph. Use the visible vertex buttons as a keyboard alternative for selecting the query source.

Assumptions, boundaries and costs

This is an unweighted, static directed graph model bounded to one through eight vertices for inspection. Reachability and membership use exact integer vertex IDs, with no numerical approximation or random simulation. Changing an arrow recomputes the model; this is not an incremental SCC data structure.

• Vertex count accepts decimal digits only. Each nonempty edge line contains exactly two nonnegative integer IDs below that count. Empty lines are ignored, duplicate arrows count once, and self-loops are accepted. Invalid raw text stays visible while previous results and the diagram disappear.
• Self queries have a path of length zero. An isolated vertex is one SCC; a self-loop does not add another class. All singleton classes do not by themselves prove the original graph acyclic, because singleton self-loops are allowed.
• Shortest query witnesses use ascending-neighbor BFS, so one representative path is shown when several tie. SCC membership does not depend on which shortest witness is chosen. Undirected or weak connectivity ignores arrow direction and answers a different question.
• The two DFS passes take O(V + E) time with adjacency lists. This teaching implementation also sorts neighbors and canonical labels, copies small replay snapshots, computes query paths and draws the graph. These extra costs are outside the linear core algorithm claim.
• Node positions, distances and component colors have no graph-theoretic weight. A crossing of drawn arrows creates no vertex. Drags keep node centers separated so their rings and arrow endpoints remain distinct. Reciprocal arrows bend apart; self-loops curve above their vertex. Dense custom graphs can still have overlapping arrows, so use the explicit edge list and path witnesses to resolve direction.
• Replay colors show the final partition from the start. The active white ring and gold stack rings show the current frame, and the discovered-tree text shows only second-pass assignments made so far. Manual navigation and input changes cancel playback timers.

Primary course references

These references support the definitions and algorithm. The six-vertex worked example, edits, exact partitions and native-control experiment above were calculated independently for this module.

• CMU 15-451/651, Depth First Search and Strong Components, November 1, 2018, section 4: mutual reachability, length-zero paths, equivalence classes and the acyclic component graph.
• University of Pennsylvania CIS 1210 course notes, chapter 19, section 19.2 (October 7, 2026 draft inspected): original-graph-first Kosaraju, decreasing finish order and the second transpose search.
• Paulo Feofiloff, IME-USP: Algoritmo de Kosaraju para componentes fortes, updated April 30, 2019: equivalent two-pass orientations, transpose invariance, extreme cases and testing against an independent reachability method.