Stack Exchange network consists of 183 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.
@badboul - yes, the case where X has just one node to remove is straight forward constant time operation, but as soon as there are more than 1 holes, it becomes tricky and it seems like relying on floodfill after apply X and Y operations is the only way to go.
@ChandraChekuri looks like the paper you linked wont be helpful.. It suggests a theorem to do MST calculation in log^4 (N) but log^4 (N) > N for N < 5000 or so.. My graph would never have V+E > 5000 ..
@badboul In my practical use case, i am mostly dealing with single digit X and Ys while V+E can reach 100+ but the main reason why I want to optimize over N floodfills is because N can reach to billions.
@ChandraChekuri None of the literature that I've come across solves for what i am asking in the question. If you've seen something similar, mind sharing the paper titles? Most of the dynamic data structures worry about queries around biconnectivity or connectivity between two vertices. I am asking for something much more simpler and probably that can be done in much more efficient manner. or if you know how I can reuse the literature and retrofit them in my use-case, please add an answer.
