Question

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, S, T, V}, {R}, {U}
• C. {P, Q, R, S, T, V}, {U}
• D. {P, Q, R, S, T, U, V}

Answer 1

The correct option is C {P, Q, R, S, T, V}, {U}

To find strongly connected component apply DFS on graph and find longest cycle. If you find a cycle in the reverse direction of every edge and again apply the DFS, if you found cycle this time also. Then this cycle is strongly connected component.


Now change direction of every edge


So, 2 strongly connected components {P, Q, V, T, S, R} and {U} are present.