Strongly Connected Components

Kosaraju's Algorithm

Find Strongly Connected Components (SCCs) in a directed graph using two passes of Depth-First Search (DFS).

Core idea

Kosaraju's algorithm uses two DFS passes.

First pass finds the finishing times of nodes in the original graph.

Second pass runs DFS on the transposed (reversed) graph in order of decreasing finishing time.

Run DFS on the original graph and push finished nodes to a stack.
Reverse the direction of all edges to create a transposed graph.
Pop nodes from the stack and run DFS on unvisited nodes in the transposed graph.
Each resulting DFS forest is a Strongly Connected Component.

Directed

Worst Case TimeO(V+E)

Worst Case SpaceO(V)

Higher score indicates more operations or complex data structures involved in the worst case.

ADJACENCY LIST (directed — outgoing only)

[1]
[2, 3]
[0]
[4]
[3]

ADJACENCY MATRIX (asymmetric for directed)

matrix[u][v] = 1 means edge u → v exists. Asymmetry indicates directed edges.

0: [1]

1: [2, 3]

2: [0]

3: [4]

4: [3]

Enter edges (source,target,weight)

Adjacency Matrix

Adjacency List

BFS

DFS

Dijkstra

Bellman-Ford

Floyd-Warshall

Prim

Kruskal

Topological Sort

Tarjan's Algorithm