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: