Kosaraju's Algorithm

Explanation

- **Kosaraju's Algorithm** is used to find the **strongly connected components (SCC)** of a directed graph. It works by performing two depth-first searches (DFS).

-

• Steps:

  • Perform DFS on the original graph to get the finish times of each vertex.
  • Reverse all edges in the graph.
  • Perform DFS on the reversed graph in the order of decreasing finish times from the first DFS to identify SCCs.

• Time Complexity:

  • O(V + E), where V is the number of vertices and E is the number of edges.