Space Complexity Summary

Space complexity for SCC algorithms is $O(V + E)$. Kosaraju: Visited array ($O(V)$), finish time stack ($O(V)$), transpose adjacency list ($O(E)$), and second visited array ($O(V)$). Total: $O(V + E)$. Tarjan: Arrays for $disc$, $low$, $on\_stack$ (each $O(V)$), stack for current path ($O(V)$), and adjacency list ($O(E)$).

Total: $O(V + E)$. Condensation graph: Worst case $O(E)$ edges if no edges collapse (e.g., DAG with no SCCs of size $> 1$).