Computing Strong Components in a Graph

A directed graph is said to be strongly connected, if you can get to any node from any other node. Or a graph could contain such maximal regions with strongly connected components (there is a path from u to v and from v to u) within it.

If you call DFS from the right node on the graph, it will possibly give you an SCC; else it might capture a union of SCCs and not give you any information at all.

Kosaraju's Two-Pass Algorithm

Warning:
How do you process the node in the decreasing order of finishing times in the 2nd pass?
You don't want to sort the nodes cos that would take nlogn time. You need to remember the finishing times [in the first pass] in some fashion so all you need to do is a linear scan.

Pseudo Code:
DFS-Loop (graph G)
-global variable t = 0 [to compute finishing times in Pass 1]
-global variable s=NULL [to keep track of leaders in Pass 2]
-Assume nodes labelled 1 to n
-for(i=n; i>=0; i--)
  - if i not yet explored
  - s = i
  - DFS(G,i)

DFS(graph G, node i)
- mark i as explored
- set leader(i) = node s
- for each arc (i,j) that is part of G:
  - if not yet explored:
    - DFS(G,j)

- t++
- set f(i) := t 

Source code in C: here