Questions: Strongly Connected Components: Kosaraju and Tarjan Algorithms

Question 1

In Kosaraju's algorithm, why are vertices processed in *decreasing* order of their first-pass finish times during the second DFS on the transpose graph?

• A. To ensure vertices with more edges are processed first, improving cache efficiency
• B. To guarantee each DFS tree in the second pass explores exactly one SCC, starting from a source SCC in the component DAG
• C. To avoid revisiting vertices already assigned to an SCC during the first pass
• D. To replicate the topological ordering of the original graph within the transpose

Answer: (B)

The vertex with the highest first-pass finish time belongs to a 'source' SCC in the condensed DAG — an SCC with no incoming edges from other SCCs. In the *transpose* graph, that source SCC becomes a sink (all its edges are reversed). Running DFS from this vertex in the transpose therefore cannot escape the SCC's boundaries — there are no transposed edges pointing outward. Once that SCC is identified and removed, the next highest-finish-time vertex is the source of the next SCC in the remainder. This ordering guarantees correct decomposition with no complex bookkeeping.

Question 2

In Tarjan's algorithm, a vertex v is identified as the root of an SCC when its low-link value equals its own discovery index. What does this condition mean?

• A. v has no outgoing edges remaining in the DFS tree
• B. v was the very first vertex discovered in the entire DFS traversal
• C. No vertex in v's DFS subtree can reach an ancestor above v via a back edge — the SCC is 'closed' at v
• D. v has the maximum discovery index among all vertices currently on the stack

Answer: (C)

The low-link value of vertex v is the smallest discovery index reachable from v through its DFS subtree and back edges. If low[v] == disc[v], no descendant of v has a back edge to an ancestor *above* v — equivalently, the group of vertices rooted at v in the DFS tree cannot 'escape' to an earlier part of the search. This means v is the topmost vertex of a maximal set of mutually reachable vertices: an SCC. Everything on the stack from v upward forms that SCC. Options A and B don't relate to low-link semantics; D confuses discovery index with stack position.

Question 3

If a directed graph has exactly one strongly connected component, then every vertex can reach every other vertex via directed paths.

• T. True
• F. False

Answer: True

By definition, an SCC is a maximal set of vertices where every vertex can reach every other vertex. If the entire graph is a single SCC, then for any two vertices u and v, there are directed paths from u to v and from v to u. The 'maximal' qualifier just means no additional vertices can be added — here there are none to add. A graph with exactly one SCC is called a strongly connected graph.

Question 4

Reversing most edges in a strongly connected graph produces a graph that is no longer strongly connected.

• T. True
• F. False

Answer: False

The transpose (edge-reversal) of a strongly connected graph is still strongly connected. If there is a directed path u → ... → v in the original, there is a directed path v → ... → u in the transpose (traverse the reversed edges in reverse order). Since the original has directed paths in both directions between every pair of vertices, so does its transpose. This property is precisely what Kosaraju's algorithm exploits: SCCs are preserved under edge reversal, but cross-component edges change direction, turning sources into sinks.

Question 5

Why does Kosaraju's algorithm use the *transpose* graph (reversed edges) in its second pass rather than running DFS on the original graph again?

Model answer: In the original graph, a DFS from the source SCC (highest finish time) would follow edges into other SCCs, mixing multiple components in a single DFS tree. In the transpose, edges between SCCs are reversed: the former source SCC is now a sink with no outgoing cross-component edges. Therefore, DFS from that vertex in the transpose stays confined to exactly that SCC. The transpose blocks cross-component travel while preserving intra-component reachability (since SCCs are strongly connected and transpose-invariant), so each DFS tree in the second pass is exactly one SCC.

The two passes work together: the first encodes reachability information in finish times; the edge reversal ensures DFS cannot leak across component boundaries in the second pass. The elegance is that no special data structure is needed — just two standard DFS traversals on the original and its transpose, both O(V + E).