Questions: Strongly Connected Components

Question 1

Vertex v in a digraph has no outgoing edges and no self-loop. What is v's strongly connected component?

• A. v is part of the SCC containing all vertices that can reach v
• B. v forms a trivial SCC containing only itself
• C. v cannot be part of any SCC because it has no outgoing edges
• D. v belongs to whichever SCC has a vertex with an edge pointing to v

Answer: (B)

Every vertex belongs to exactly one SCC — even if it cannot reach any other vertex. Since v has no outgoing edges, no other vertex is reachable from v. The only vertex reachable from v is v itself (trivially, via a path of length 0). So the largest subset with mutual reachability involving v is just {v}. Trivial SCCs of size 1 are common in digraphs, especially for source-like or sink-like vertices.

Question 2

Why is the condensation digraph (the DAG formed by collapsing each SCC to a node) always acyclic?

• A. Because DFS on the reversed graph processes SCCs in topological order
• B. Because the original digraph has no cycles, only directed paths
• C. Because if two SCCs had a cycle between them, all their vertices would mutually reach each other, making them one SCC — contradicting maximality
• D. Because each SCC has a unique finish time in Kosaraju's algorithm

Answer: (C)

This is the key structural reason. Suppose two distinct SCCs, C₁ and C₂, had edges C₁→C₂ and C₂→C₁ in the condensation. Then every vertex in C₁ could reach every vertex in C₂ (via the inter-SCC edges) and vice versa. That means all vertices of C₁ ∪ C₂ mutually reach each other — so they would form a single SCC, contradicting the assumption that C₁ and C₂ are distinct. Therefore no cycles can exist in the condensation.

Question 3

In a strongly connected digraph, every pair of vertices can reach each other via directed paths.

• T. True
• F. False

Answer: True

By definition, a strongly connected graph is one where the entire vertex set forms a single SCC — i.e., every vertex is reachable from every other vertex following directed edges. This is the meaning of 'strongly connected': mutual reachability holds globally. (Compare to 'weakly connected,' which only requires connectivity when edge directions are ignored.)

Question 4

If vertices u and v are in the same strongly connected component, there should be a direct edge from u to v and from v to u.

• T. True
• F. False

Answer: False

SCCs require mutual reachability via directed *paths*, not direct edges. u and v can be in the same SCC if there is a directed path u → w₁ → w₂ → v and a separate path v → x₁ → u, even if no direct u↔v edges exist. Requiring direct edges would be a much stricter condition (essentially requiring a tournament-style structure), and most real SCCs involve multi-hop paths.

Question 5

Explain why the condensation of a digraph is always a DAG, and why this property is useful.

Model answer: The condensation is a DAG because any cycle in the condensation would imply that two or more SCCs are mutually reachable, which would mean they should be merged into a single larger SCC — contradicting the maximality requirement. The DAG property is useful because DAGs support topological sorting, allowing you to determine a valid ordering of tasks or dependencies. It also reveals the large-scale causal or flow structure of the original digraph: which components influence others, and whether feedback is possible.

The condensation transforms a complex digraph with cycles into a hierarchy. Once cycles are identified and contracted, what remains is a pure flow structure with no mutual dependencies — every edge in the condensation points 'forward' in some topological sense. This is why SCC decomposition is the first step in many graph algorithms, including those that compute reachability, scheduling order, or influence propagation.