Decremental Strongly-Connected Components and Single-Source Reachability in Near-Linear Time

Aaron Bernstein, Maximilian Probst, Christian Wulff-Nilsen

Computing the Strongly-Connected Components (SCCs) in a graph $G=(V,E)$ is known to take only $O(m+n)$ time using an algorithm by Tarjan from 1972[SICOMP 72] where $m=|E|$, $n=…