Senior LevelData Structures & Algorithms
How does Kosaraju's Algorithm find Strongly Connected Components?
ā Interview Prompt: Explain Strongly Connected Components (SCCs), Kosaraju's two-pass DFS algorithm, and its O(V+E) complexity.
A Strongly Connected Component (SCC) is a maximal set of vertices where every vertex is reachable from every other.
Kosaraju's Algorithm (Two-Pass DFS):
1
Pass 1: DFS on original graph. Push vertices to a stack in finish order (postorder).
2
Reverse the graph (transpose all edges).
3
Pass 2: Process vertices from the stack. Each DFS from an unvisited vertex on the reversed graph discovers one SCC.
ā¢
Time: $O(V + E)$, Space: $O(V + E)$.
Code Implementation Example
typescript
function kosarajuSCC(n: number, edges: [number, number][]): number[][] {
const adj: number[][] = Array.from({ length: n }, () => []);
const radj: number[][] = Array.from({ length: n }, () => []);
for (const [u, v] of edges) { adj[u].push(v); radj[v].push(u); }
const visited = new Array(n).fill(false);
const stack: number[] = [];
function dfs1(u: number) {
visited[u] = true;
for (const v of adj[u]) if (!visited[v]) dfs1(v);
stack.push(u);
}
for (let i = 0; i < n; i++) if (!visited[i]) dfs1(i);
visited.fill(false);
const sccs: number[][] = [];
function dfs2(u: number, scc: number[]) {
visited[u] = true;
scc.push(u);
for (const v of radj[u]) if (!visited[v]) dfs2(v, scc);
}
while (stack.length) {
const u = stack.pop()!;
if (!visited[u]) {
const scc: number[] = [];
dfs2(u, scc);
sccs.push(scc);
}
}
return sccs;
}š”Kosaraju's two-pass DFS SCC detection in O(V+E).
šÆ Interview Key Takeaway
Kosaraju's SCC uses two DFS passes and a graph transpose. SCCs compress a directed graph into a DAG ā essential for circuit analysis and dependency resolution.
#DSA#SCC#Kosaraju#Graph#Senior
Back to all Data Structures & Algorithms Questionsā