Problem
I have an undirected graph (with multi-edges), which will change over time, nodes and edges may be inserted and deleted. On each modification of the graph, I have to update the connected components of this graph.
Properties
Additional properties are that no two components will ever be reconnected. Obviously, the graph can have cycles to an arbitrary amount (otherwise the solution would be trivial). If an edge $e$ does not contain a node $n$, it will never adopt that node. However, if $n \in e$, it can change to $n \notin e$.
Approaches
I have two possible approaches so far, but as you will see they are horrible:
Slow state-less
I can search (dfs/bfs) the graph starting from the modified element(s) every time. This conserves space, but is slow as we have O(n+m) for each modification.
Stateful fast(-er) (?) approach
I can store all possible paths for each node to all possible nodes, but if I see it correctly, this will take O(n^4) memory. But I am not sure how the runtime improvement is (if there is one at all, because I have to keep the information up-to-day for every node in the same component).
Question
Do you have any pointers, how I can learn more about that problem or perhaps some algorithms I can build on?
Note
If there is a vast improvement in runtime/memory I could live with a non-optimal solution that sometimes says two components are one, but of course I would prefer an optimal solution.