2023-213

 Considering the following directed graph:

I. Since this is a strongly connected graph, it does not have a topological sort.

II. We can easily find a topological sort for this graph using the reverse order of finishing times from DFS.  

III. By applying Kosaraju-Sharir’s algorithm to this graph, we will obtain a set of strongly connected components in the order [{C}, {D, E, F}, {A}, {B}].

IV. Kosaraju-Sharir’s algorithm can find the topological sort of any directed graph even if it has cycles, in this case treating each strongly connected component as a single node. In this particular graph, the last node in the topological sort could be either A or B.

What statements from the options above are correct?

1. I and III
2. II and IV
3. III
4. III and IV
5. none of above

Original idea by: Anderson Nogueira Cotrim