Is there a proper algorithm to solve edge-removing problem?

Question

There is a directed graph (not necessarily connected) of which one or more nodes are distinguished as sources. Any node accessible from any one of the sources is considered 'lit'. Now suppose one of the edges is removed. The problem is to determine the nodes that were previously lit and are not lit anymore.

An analogy like city electricity system may be considered, I presume.

Answer 1

This is a "dynamic graph reachability" problem. The following paper should be useful:

A fully dynamic reachability algorithm for directed graphs with an almost linear update time. Liam Roditty, Uri Zwick. Theory of Computing, 2002.

This gives an algorithm with O(m * sqrt(n))-time updates (amortized) and O(sqrt(n))-time queries on a possibly-cyclic graph (where m is the number of edges and n the number of nodes). If the graph is acyclic, this can be improved to O(m)-time updates (amortized) and O(n/log n)-time queries.

It's always possible you could do better than this given the specific structure of your problem, or by trading space for time.