Noesis
3.5.8 · D5Graphs

Question bank — Strongly Connected Components (SCC) — Kosaraju's algorithm, Tarjan's algorithm

1,494 words7 min read↑ Back to topic

True or false — justify

Two nodes with only the edge (no path back) are in the same SCC.
False — an SCC needs paths both ways; without they sit in two different singleton SCCs.
A single vertex with no edges is an SCC by itself.
True — it trivially reaches itself (empty path), so every isolated vertex is its own SCC of size 1.
The condensation of any directed graph is always a DAG.
True — if the condensation had a cycle among super-nodes, those SCCs would be mutually reachable and merge into one, contradicting maximality.
If a directed graph is already a DAG, every vertex is its own SCC.
True — a DAG has no directed cycle, so no two distinct nodes are mutually reachable; each SCC has size 1.
Reversing all edges of a graph changes which vertices belong to each SCC.
False — if and in , both reverse into paths too, so the SCC partition is identical in and .
SCCs of a graph are the same as connected components of the underlying undirected graph.
False — undirected connectivity only needs a path; that graph's "weakly connected" pieces can each contain many SCCs.
Every edge of the original graph stays inside a single SCC after condensation.
False — only edges between mutually reachable nodes stay internal; cross-SCC edges become the DAG's edges.
In Tarjan, low[u] can ever be larger than disc[u].
False — low[u] starts equal to disc[u] and only ever takes a min, so low[u] ≤ disc[u] always.
Kosaraju needs the graph reversed exactly once.
True — one reversal, then the second DFS runs on that reversed graph in decreasing finish order; reversing twice would undo it.
Tarjan and Kosaraju always return SCCs in the same order.
False — both find the same set of SCCs, but Tarjan emits them roughly in reverse topological order of the condensation while Kosaraju's order depends on finish times; the partition matches, the sequence need not.

Spot the error

"Tarjan: on a back/cross edge to , do low[u] = min(low[u], low[v])."
Wrong — low[v] may point into an already-popped SCC, wrongly merging two components. Use disc[v], and only when onStack[v] is true.
"Tarjan: update low[u] from disc[v] on every non-tree edge."
Wrong — you must guard with onStack[v]. An edge into a finished (popped) node must be ignored, else you merge separate SCCs.
"Kosaraju: run the second DFS on the original graph, decreasing finish order."
Wrong — it must run on the reversed graph. On itself the source SCC's DFS leaks into everything it reaches.
"Kosaraju: run the second DFS on the reversed graph in the same order as pass 1."
Wrong — the correctness theorem needs decreasing finish time. Same order can start inside a non-source SCC and a tree leaks across boundaries.
"Tarjan: pop the whole stack once at the very end to emit SCCs."
Wrong — SCCs are emitted incrementally each time low[u] == disc[u], popping only down to . One final pop would report the whole graph as one SCC.
"Kosaraju: push onto the finish-order list when you first visit it."
Wrong — push on return (after all descendants finish). Finish time must reflect subtree completion, not discovery.
"Tarjan needs an explicit visited array separate from disc."
Redundant — disc[u] being set (e.g. ) already means "visited." A separate flag is not the bug, but onStack is a distinct concept you cannot drop.
"For a self-loop , Tarjan should skip it entirely."
Harmless but note: is on the stack, so low[u] = min(low[u], disc[u]) changes nothing; still forms a size-1 SCC. Skipping is fine, mishandling it is not.

Why questions

Why does the highest-finish-time vertex belong to a source SCC of the condensation?
If an SCC can reach ( in the DAG), then ; so the global max finish lies in an SCC with nothing pointing to a later one — a source.
Why is that source SCC a sink in the reversed graph, and why does that matter?
Reversing flips all its outgoing edges to incoming, so the second DFS cannot escape it — the DFS tree is exactly one SCC, then we peel it off and repeat.
Why does Tarjan use low[v] for tree edges but disc[v] for stack edges?
A tree child's full subtree info (low[v]) legitimately extends the current path; a back/cross edge lets you use only one jump, and only to a node still in the current component — hence disc[v], guarded by onStack.
Why does low[u] == disc[u] prove is an SCC root?
It means cannot loop back to any earlier-discovered node in the current component; so is the highest (entry) node of its SCC and everything above it on the stack completes that SCC.
Why can't we just run one DFS and call each DFS tree an SCC (no low, no reversal)?
A single DFS tree can span multiple SCCs (edges leaving a sink SCC lead onward). Without finish-order+reversal (Kosaraju) or low+stack (Tarjan) you cannot draw the boundaries.
Why does the condensation being a DAG make it useful?
Once cycles collapse, you can run Topological Sort and DAG-only algorithms (longest path, DP over the order) — the whole point of SCC as a "remove the cycles" preprocessing step.
Why does dropping onStack break Tarjan even if everything else is correct?
Without it, an edge into an already-finished SCC updates low[u] toward that dead component, falsely merging it with the current one.
Why is 2-SAT solved with SCCs rather than plain connectivity?
A variable and its negation being mutually reachable (same SCC) means a contradiction — that requires directed both-ways reachability, exactly what SCC captures, not weak connectivity.

Edge cases

A graph that is one big cycle : how many SCCs?
Exactly one SCC of size — every node reaches every other around the cycle, so it is maximal and single.
A graph with no edges at all ( isolated vertices): how many SCCs?
SCCs, each a single vertex; the condensation is disconnected nodes (still trivially a DAG).
Two disjoint cycles with no edge between them: SCC count and condensation shape?
Two SCCs; the condensation is two isolated super-nodes (no DAG edge, since no cross edge exists).
A node with a self-loop only (, nothing else): its SCC?
A size-1 SCC — the self-loop makes , but no other node joins it.
Does Kosaraju handle a disconnected directed graph correctly?
Yes — the outer loop restarts DFS on any unvisited vertex, so every component (and every SCC inside it) is processed.
An empty graph (zero vertices): what should both algorithms output?
An empty list of SCCs; the loops never run, which is the correct degenerate result.
A graph where every SCC has size 1 but many edges exist (a DAG): does Tarjan still emit SCCs?
Yes — no node satisfies mutual reachability, so each pops alone with low[u] == disc[u] at its own frame.
Parallel edges appearing twice: do they change the SCCs?
No — reachability is unchanged by duplicate edges; both algorithms give the identical partition (though they cost one extra edge visit).
Recall One-line self-test before you move on

If you can state why disc (not low) guards a stack edge, why the reversed graph makes a source into a sink, and why self-loops and empty graphs still behave — you have the traps covered. The single deepest trap ::: Using low[v] on a stack edge in Tarjan — it silently merges separate SCCs and passes small tests, so it is the bug you will actually ship.