Graph Algorithms

Strongly Connected Components

In a directed graph, a strongly connected component is a maximal group where every vertex can reach every other — Kosaraju's finds them with two DFS passes, Tarjan's with a single pass using low-link values.

SCC: every vertex in the component can reach every other vertex in the same component, following edge directions
Kosaraju's algorithm: DFS to compute finish order, reverse every edge, DFS again in decreasing finish order — each DFS tree in the second pass is one SCC
Tarjan's algorithm: a single DFS pass tracking discovery time and "low-link" (lowest reachable discovery time) — no graph transpose needed
Collapsing each SCC into a single node always yields a DAG — the condensation graph — which is what Topological Sort then orders
Not the same as connected components in an undirected graph — direction matters: a → b doesn't imply b can reach a

Kosaraju's vs Tarjan's
	Kosaraju's	Tarjan's
DFS passes	two (plus building the transpose graph)	one
Extra structure	transposed adjacency list	a stack + low-link array
Conceptual load	simpler to prove correct	simpler to implement once understood, harder to derive from scratch

Condensing SCCs into a DAG (sketch)

List<Integer> sccOf = computeSccIds(graph);         // e.g. via Kosaraju's or Tarjan's
int sccCount = Collections.max(sccOf) + 1;
Set<Integer>[] condensationAdj = new Set[sccCount];
for (int i = 0; i < sccCount; i++) condensationAdj[i] = new HashSet<>();
for (int u = 0; u < graph.size(); u++) {
    for (int v : graph.get(u)) {
        if (!sccOf.get(u).equals(sccOf.get(v))) {
            condensationAdj[sccOf.get(u)].add(sccOf.get(v));   // edge between two different SCCs
        }
    }
}
// condensationAdj is now guaranteed acyclic — safe to topologically sort