Andrii Stolitnii
We give a randomized decremental data structure for directed graphs that maintains strongly connected components and single-source reachability under edge deletions in total expected O(m log4 n) update time and O(1) query time (against an oblivious adaptive adversary). The algorithm maintains a multi-level hierarchy of contracted graphs based on a monotone separator chain; when an SCC becomes "large" in an S-distance metric, a small separator is promoted to the next level to split it. Within each SCC it maintains generalized Even–Shiloach trees in the S-distance setting (where the separator acts as a feedback vertex set), and uses random centers plus reuse after splits so each vertex participates in only O(log n) trees in expectation, yielding the near-linear total update bound.