Questão 5 - Kosaraju-Sharir's algorithm
Kosaraju-Sharir's algorithm is designed to find all Strongly Connected Components (SCCs) in a directed graph. It uses two main depth-first searches (DFS) to accomplish this. Which of the following steps correctly describe the main phases of the algorithm? A - Perform a DFS on the graph to compute the finishing times of each vertex. Then, reverse the graph and perform another DFS based on decreasing finishing times. B - Perform a BFS (Breadth-First Search) on the graph, followed by sorting the nodes based on their distances from the start vertex. Then, reverse the graph and repeat the BFS. C - Reverse the graph, perform a DFS, and then compute a topological sort of the graph to find SCCs. D - Use Dijkstra's algorithm to find the shortest path to each vertex, then reverse the graph and repeat the process. E - None of above