2023-215

Given the following directed graph, if we executed Kosaraju-Sharir’s algorithm to detect its strongly connected components (SCCs) starting at node A and assuming the adjacency lists are sorted in descending order (Z to A), what would the SCCs be and in which order they would be returned?

1. 2 SCCs returned: BDCA first and then FGH;
2. 2 SCCs returned: FGH first and then BDCA;
3. 4 SCCs returned: H first, then G, F, and BDCA;
4. 4 SCCs returned: BDCA first, then F, G, and H;
5. None of the above.

Original idea by: Fillipi Valadares