Question 4. Strongly Connected Components

 

Based on figure above, we can assert:

I. If we apply Kosaraju-Sharir's algorithm, it will return 5 strongly connected components (SCCs), when we assume the node's list are sorted in descending order.

II. The component {G, J, I} is not a SCCs because it is inside the component {G, H, K, L, J, I}

III. If there is a direct link from node I to node A, we would just have 4 SCCs.

IV. If there is a direct link from node D to node C, the SCC {C, F} would still exist.

Which statements from the options above are correct?

 A. I, II, III and IV

 B. II and IV

 C. I, II, IV

 D. II and III

 E. none of above

Original idea by: Germán Darío Buitrago Salazar