Which of the following is the correct decomposition of the directed graph…
2006
Which of the following is the correct decomposition of the directed graph given below into its strongly connected components?
- A.
{P, Q, R, S}, {T}, {U}, {V}
- B.
{P,Q, R, S, T, V}, {U}
- C.
{P, Q, S, T, V}, {R}, {U}
- D.
{P, Q, R, S, T, U, V}
Attempted by 57 students.
Show answer & explanation
Correct answer: B
Method: Use a standard strongly connected components algorithm (for example, Kosaraju's or Tarjan's algorithm).
Run a DFS to compute finishing times (Kosaraju) or run Tarjan's single-pass algorithm to extract SCCs.
If using Kosaraju: reverse all edges and perform DFS in order of decreasing finish time; each DFS tree in the reversed graph is one strongly connected component.
Result:
The strongly connected components are {P, Q, R, S, T, V} and {U}.
Explanation:
All nodes P, Q, R, S, T and V are mutually reachable: following the directed edges in the graph you can find a path from any one of these nodes to any other, so they form a single strongly connected component.
Node U is not mutually reachable with that group: although there are edges between U and the other nodes in one direction, U cannot reach back to some nodes (or they cannot reach U), so U stands alone as its own strongly connected component.
Therefore the correct decomposition is: {P, Q, R, S, T, V}, {U}.