Problem at hand:Finding separate subgraphs. Update on adding or removing edges.First I've been thinking about running DFS after every operation from both ends of the edge, but if I keep information about subgraph in the vertices, then adding edge is O(1); you just join subgraphs of both ends.Now, if I wanted to remove the edge I would still have to DFS/BFS (O(E+V), I believe) and see if there is another path between the ends of the edge. How do I transfer this responsibility from CPU to RAM? Is it worth it?Edit: System explanationBased on Circuitry from the game Factorio. Basically I have objects with input and output. Every tick, if input changed, output is recalculated based on criteria within the object. I can connect inputs, outputs and poles (simple vertex) with two types of wiring, each treated separately, but summed up within input. If I connect multiple outputs with same wire, whole network (subgraph) transfers sum of all outputs. On top of that I want to compile a setup of objects into blueprint, which is basically a new object with custom input and output count.I treat types of wiring as 2 separate graphs, and find 2 types of networks. Network holds references to all outputs (or single summed up output) and inputs. Basically I only need to divide everything into networks. For removing a wire DFS/BFS would probably work just fine, but I've been wondering if there is a memory based solution.
Finding subgraphs in non-directed graph
graph