Skip to main content

Connected and Strongly Connected Components

What This Concept Is​

Undirected connected components group vertices by reachability. Directed SCCs group vertices by mutual reachability: u reaches v and v reaches u. Weak components instead ignore direction. SCCs partition all declared vertices, including isolated ones. Contracting them gives a DAG: a cycle among components would make them mutually reachable and contradict maximality.

Why It Matters Here​

SCCs identify cyclic dependency regions without falsely labeling every downstream task as cyclic. The condensation graph supports ordering between regions, but contracting a cycle does not make its internal dependency constraints executable.

Concrete Examples​

For 0→1,1→0,1→2,2→3 with isolated 4, SCCs are {0,1},{2},{3},{4}. Ignoring direction merges 0 through 3 into one weak component; source reachability from 0 also visits 0 through 3, but neither is the SCC partition.

Kosaraju variant used here: DFS G and collect finish order; reverse every edge; process roots in decreasing original finish time on the transpose. For a condensation edge C→D, C's maximum finish time exceeds D's. Therefore the next unvisited component in that order cannot reach another unvisited component in the transpose; its search finds precisely its own SCC. Two traversals and transpose construction take O(V+E).

Common Confusion / Misconceptions​

Tarjan's active component stack is not the same as the current recursion stack. For an unvisited child, recurse and combine its lowlink; for an already discovered vertex still on the component stack, combine its discovery index. Ignore edges to vertices already assigned to completed components. The active-stack condition is essential; a loose "at most one back edge" description is not enough to code it.

How To Use It​

Accept component order and labels as arbitrary. Verify that each vertex appears once, each group has mutual reachability, and no two groups could be merged under that relation. In tiny tests, a reachability matrix supplies an independent oracle. Use Kosaraju for the core lab; Tarjan is a separately proved extension.

Check Yourself​

  1. Why is the condensation graph acyclic?
  2. Which graph is used for each pass in this Kosaraju variant?
  3. How can weak connectivity disagree with strong connectivity?
  4. Why is Tarjan's on-stack condition different from DFS gray state?

Mini Drill or Application​

Implement SCCs, build a deduplicated condensation graph, and topologically order its component vertices. Test a one-way chain between cycles and a disconnected cycle. Deliberately omit transposition and find a failing directed graph. See P7.

Read This Only If Stuck​

Find strong components, Kosaraju, and Tarjan invariants in Skiena, CLRS, or Sedgewick and Wayne. These are book indexes, not exact section links. The reading guide names bounded assignments and local source files. Attempt the worked examples before adding more reading.