Quiz question 5 (05/05/2023) - Strongly Connected Components

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 the topological sort from this graph using the reverse order of finishing time from DFS.  

III. By applying Kosaraju-Sharir’s algorithm to this graph, we can 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 and IV
  4. III
  5. none of above
Original idea by: Anderson Nogueira Cotrim

Comments

Post a Comment