Articles
Strongly Connected Component Interview Questions: Cycles and Condensation Graphs
Practice strongly connected component interview questions with Tarjan stack invariants, cycle evidence, condensation DAGs, and independent graph checks.
A dependency graph contains a cycle. You return the vertices left over after topological sorting and call them “the cycle.” That answer can include jobs merely blocked behind the cycle, while missing the distinction between several separate cyclic groups.
Strongly connected component interview questions ask for maximal mutual reachability, then for the decisions that become possible after those groups are contracted. A cycle witness proves one problem exists. An SCC partition describes every vertex's membership, including isolated vertices and singletons.
The technical facts below come from the linked Princeton Algorithms and NetworkX documentation, checked September 30, 2026. The graphs, traces and preparation advice are original examples and inference. No candidate reports establish an employer's interview format or the frequency of these questions.
Extend the answer from one cycle to a complete partition and an explanation of downstream impact.
What makes a component strongly connected and maximal?
Reference fact: vertices belong to the same SCC when each can reach the other through directed paths. Components are maximal under that relation. Princeton describes strong connectivity as an equivalence relation that partitions the vertices. Directed graph definitions
For an original contract exercise, take A→B, B→A and B→C. A and B form one component. C is separate: reaching C from B does not establish a return path. Ignoring arrow direction would answer a different, weak-connectivity question.
“Maximal” does not mean “largest component in the graph.” It means you cannot add another vertex while retaining mutual reachability. Return all groups unless the prompt asks only for the largest. Include nodes listed in the input even if no edge mentions them.
A singleton is still an SCC because a vertex reaches itself by a path of length zero. However, it contains a directed cycle only if there is a self-loop. Thus component_size == 1 is insufficient to declare the graph acyclic.
Clarify whether the result requires component sets, a vertex-to-component map, a count or a cycle witness. Numeric IDs usually depend on traversal order. A correct partition need not reproduce another implementation's integers or output order. If stable output is required, define a separate presentation rule.
Can you partition this six-node graph correctly?
Use this original fixture with vertices A through F:
A → B
B → A, C
C → D
D → C, E
E → E
F → nothing
The partition is {A,B}, {C,D}, {E}, {F}. There are four components, three of which contain cycles. E is cyclic because of its self-loop. F is an isolated singleton and is not cyclic.
Explain both directions for the two nontrivial groups. A reaches B and B reaches A. C reaches D and D reaches C. B reaches C, but C cannot reach B, so the first two groups must remain separate. D reaches E, but E cannot leave itself.
Do not enumerate every simple cycle to obtain this answer. SCC membership groups vertices by reachability; a component may contain many overlapping cycles. Listing those cycles is a different task with potentially much larger output.
Our local Python implementations reproduce these four groups and identify E's special case. The run checks the example's graph contract; it does not demonstrate behavior on a production dependency service or execute the linked Java and NetworkX implementations.
Why must the condensation graph be a DAG?
Official API fact: NetworkX defines condensation by contracting each SCC into one node. Its documentation states that the result is a DAG and exposes both original-node membership and a mapping to contracted nodes. Condensation documentation
For our fixture, retain only the cross-component edges:
{A,B} → {C,D} → {E}
{F} isolated
The self-loop on E disappears from the condensation edge set. Internal edges belong to the contracted group; retaining them as self-loops would defeat the DAG representation. Multiple original edges between the same two groups can become one edge when the contract asks for a simple condensation graph.
Here is an original proof to rehearse. Suppose several distinct contracted groups formed a directed cycle. From any group on that cycle, you could reach the next group and eventually return. Internal strong connectivity lets you connect the entry and exit vertices within each group. Those groups would therefore be mutually reachable and should have been one SCC. The assumed distinctness is a contradiction.
The contracted graph permits ordering between groups. It does not supply a legal dependency order inside a cyclic group. That requires a changed dependency model, a joint processing strategy or an explicit error, depending on the application's rules.
Why does Tarjan need an active stack as well as visited state?
Reference fact: Princeton's Tarjan implementation performs one DFS-based SCC computation in linear time. Its implementation prevents finalized components from lowering an unfinished component's values by assigning popped vertices a sentinel value. Tarjan implementation
In our original implementation, maintain discovery indices, low-link values, a stack and an explicit active set. An undiscovered neighbor starts recursive exploration. A discovered neighbor still on the active stack can lower the current low-link using that neighbor's discovery index. A neighbor already assigned to a completed component does not.
The distinction is between “seen before” and “still eligible to belong to an unfinished group.” Active SCC-stack membership is also not identical to being on the current recursive call stack: a returned DFS call can leave its vertex active until its component root is resolved.
Consider this original counterexample, with traversal starting at Y:
| Event | Necessary interpretation |
|---|---|
| Visit Y; it has no outgoing edges | Assign index 0 and finalize {Y} |
| Start X with edge X→Y | Assign index 1; X becomes active |
| Inspect already discovered Y | Y is finalized, so ignore it for low-link reduction |
| Finish X | Low-link remains 1; finalize {X} |
If you update X merely because Y was visited, you can lower X to zero and prevent X from being recognized as a root. A flawed implementation may omit a component or merge it incorrectly later. There is no Y→X path to justify any merge.
At a component root, pop through that root and assign every popped vertex to the same group. Keep the invariant attached to the update rules; memorizing a min() expression without explaining which vertices are eligible makes this counterexample difficult to debug.
How does Kosaraju differ from Tarjan?
Reference fact: Princeton's Kosaraju–Sharir implementation computes reverse postorder on the reversed graph, then searches the original graph in that order. The chapter also confirms the symmetric variant: first traverse the original graph, then the reversed graph. Both require the appropriate finishing order. Kosaraju–Sharir implementation
Our original check uses the symmetric variant. It records original-graph finishing order, then visits the reversed graph in decreasing finishing order. Each new search creates one component. Reversing edges preserves which pairs are mutually reachable, but the finishing order controls whether a search escapes into a different group.
Answer an algorithm-choice question with implementation constraints. Kosaraju requires access to reverse adjacency and two traversals. Tarjan avoids an explicit reversed graph but needs more delicate state. Neither becomes correct just because its method name appears in the answer.
Current library fact: NetworkX's stable documentation describes its SCC routine as an iterative Tarjan variant and returns a generator of component sets. Do not assume that every library uses your classroom pseudocode or returns eagerly materialized lists. SCC API documentation
For a small interview solution, choose the method whose invariants you can explain and test. For a large graph, discuss recursion limits, reverse-edge storage and the input representation before committing to an implementation.
Which checks expose plausible wrong solutions?
Use independent membership evidence. For a small graph, compute reachability from every vertex. Two vertices should share a component exactly when each appears in the other's reachable set. This oracle is slower than a linear SCC algorithm, but its simplicity makes it useful for small regression inputs.
Our executed original checks compare Tarjan and Kosaraju with that oracle on all 512 directed three-vertex graphs, including possible self-loops, and on 200 seeded six-vertex graphs with possible parallel edges. They also verify that every resulting condensation graph is acyclic. An empty input and the finalized-neighbor example pass separately.
These checks compare sets of sets, not numeric component IDs. They would reject an algorithm that returns every cycle separately, omits isolated vertices or treats a one-way edge as mutual reachability. The finite sample strengthens confidence in these implementations; it is not a proof for every possible graph.
Add focused mutations to the worked fixture. Removing E→E should change cyclic classification without changing its singleton membership. Adding E→A should merge A through E into one SCC, while F remains separate. Duplicating B→C should preserve membership, although it increases the number of stored edges scanned.
With adjacency lists, SCC computation can run in O(V+E). Our Tarjan state uses O(V) auxiliary space; constructing reverse adjacency for our Kosaraju variant additionally uses O(V+E) storage. A long directed chain can still exhaust a recursive runtime stack. An iterative DFS must preserve finishing events and resumable neighbor iteration, not simply replace recursion with arbitrary popping.
What can a dependency team decide from SCC results?
For an original scheduling scenario, use A↔B and B→C, where an arrow means “must complete before.” Kahn's algorithm cannot remove any of these vertices. Its residual set is {A,B,C}, but only {A,B} is cyclic. C is blocked downstream rather than a member of that cycle.
SCCs separate those roles. Report the cyclic group and a representative internal cycle as evidence, then use the condensation graph to identify dependent groups. Confirm the arrow convention first: if an arrow instead means “depends on,” processing and impact directions change.
A component boundary also does not tell you which edge to delete. Removing one arbitrarily chosen edge from a large SCC may leave other cycles intact. Ask which dependencies are negotiable, whether joint execution is allowed, and how a proposed repair will be revalidated.
If the interviewer changes the graph during the exercise, make the update boundary explicit. A new edge from one contracted group back to an ancestor can merge several groups. Recomputing SCCs may be adequate for the stated scale; do not promise a cheap incremental algorithm merely because the previous result was cached.
Practice the partition, proof and follow-up
| Question | SCC follow-up |
|---|---|
| Detect cycle in directed dependency graph | Return cyclic groups and downstream blocked vertices separately |
| Validate Adding an Edge to a Directed Acyclic Graph | Explain when a back-reaching edge merges groups |
| Resolve Package Dependencies with Cycle Detection | Preserve isolated packages and explain the repair contract |
| Compute Load Factors in a Service Dependency DAG | State what contraction loses before aggregating values |
| Design a Rule-Driven Process Graph Validator | Attach a cycle witness to an invalid component |
Return to the directed dependency exercise. Explain one partition, prove why its condensation is acyclic, and show the finalized-neighbor counterexample before discussing optimization.