Find all strongly connected components (Tarjan's Algorithm)?

List<List<int>> TarjanSCC(Dictionary<int, List<int>> graph) {
int time = 0;
var stack = new Stack<int>();
var onStack = new HashSet<int>();
var low = new Dictionary<int, int>();
var disc = new Dictionary<int, int>();
var visited = new HashSet<int>();
var sccList = new List<List<int>>();

void DFS(int u) {

disc[u] = time;

Follow on:

low[u] = time;

time++;

stack.Push(u);

onStack.Add(u);

visited.Add(u);

foreach (var v in graph[u]) {
if (!disc.ContainsKey(v)) {

DFS(v);

low[u] = Math.Min(low[u], low[v]);

} else if (onStack.Contains(v)) {

low[u] = Math.Min(low[u], disc[v]);
}
}
if (low[u] == disc[u]) {
var scc = new List<int>();
int w;

do {

w = stack.Pop();

onStack.Remove(w);

scc.Add(w);

} while (w != u);

sccList.Add(scc);

}
}
foreach (var node in graph.Keys) {
if (!disc.ContainsKey(node))

DFS(node);

}
return sccList;
}

Explanation:

Tarjan's algorithm finds SCCs using low-link values and DFS stack.

Follow on: