Algorithms and Data Structures · Senior · Question 34 of 75
What does Tarjan's or Kosaraju's algorithm compute?
- 1Shortest paths with negative edge weights
- 2The maximum flow between two vertices
- ✓Correct answer: Strongly connected components of a directed graph
Explanation
A strongly connected component is a group where every vertex reaches every other. Both algorithms run in O(V + E) with DFS. Collapsing SCCs turns any directed graph into a DAG, useful for dependency analysis.