Suppose you have a graph G, and you want to support the following operations:
addEdge(Node n1, Node n2)
Now I want to track after every operation what the connected components of my graph are. If I only had to support
addEdge, I would use a Union-Find data structure to maintain this information after every operation.
However, how does one support deletion operations? My current thought is that I must run several BFS operations on my graph to recompute all the connected components of the graph again.
Is there a more efficient way to support the