Which of the following is the correct decomposition of the
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 61 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}.