If these are directed graphs, then the problem/algorithm described is equivalent (unless i'm misunderstanding this explanation) to incremental 2-edge-connectivi

If these are directed graphs, then the problem/algorithm described is equivalent (unless i'm misunderstanding this explanation) to incremental 2-edge-connectivity and various queries about it. The best known algorithms are O(mn), and they are very experimental. See, e.g., various papers you'll find here: https://dblp.uni-trier.de/pers/hd/g/Georgiadis:Loukas https://dblp.uni-trier.de/pers/hd/g/Georgiadis:Loukas For undirected graphs, this is also very well studied problem , and much easier (O(m+n)).