Consider the graph shown in the figure below: Which of the following is a…
2008
Consider the graph shown in the figure below:

Which of the following is a valid strong component?
- A.
a, c, d
- B.
a, b, d
- C.
b, c, d
- D.
a, b, c
Attempted by 65 students.
Show answer & explanation
Correct answer: D
A strong component in a directed graph is a maximal subgraph where every vertex is reachable from every other vertex within that subgraph. In the given graph, nodes A, B, and C form a directed cycle (A → B → C → A). This means you can travel from any of these three nodes to the other two, making them mutually reachable. Node D has incoming edges from A and C but no outgoing edges to return to the cycle, so it cannot be part of this component. Therefore, {A, B, C} is a valid strong component.