Here is the algorithm I had in mind when I posted the question.
During the modification phase, we need to keep track of
Connected components and cycles.
For cycles, we track each as an ordered list of vertices for each cycle which does not include other cycles. A cycle is said to include another cycle if every vertex from the smaller cycle is in the larger cycle.
For connected components, we will consider one vertex as the "canonical" member of the component. As long as every component contains exactly one canonical vertex, we can flood-fill from any vertex and will reach that component's canonical vertex in finite time.
To begin with:
The list of cycles is empty.
All vertices are part of the same component, so there is only a single canonical vertex.
Whenever an edge is added:
If each end is in a different component, combine the components by un-marking the canonical vertex of one of the two components.
If both ends are currently part of the same cycle, split that cycle into two smaller cycles.
Otherwise, add a cycle to the list containing the shortest path from one end to the other that does not include the newly added edge.
Whenever an edge is removed:
If it is part of exactly one cycle, remove that cycle.
If it is part of exactly two cycles, combine those cycles into one larger cycle.
I do not believe it is possible for a single edge to be part of more than two minimal cycles.
If it is not part of a cycle, then it must be creating a new connected component. Flood fill from each end until we find a canonical vertex. Mark the vertex which did not find a canonical vertex as a new connected component.
Whenever a query is issued:
Flood fill from both ends until either both ends find different canonical vertices (disconnected), or the two searches cross eachother (connected).
The original problem, as mentioned in the question, is tracking "what's plugged in to what" in a game like Factorio - the player is adding and removing wires, and every time a wire is created or removed, we need to immediately update the network - maybe one of the sub-grids needs to shut down for lack of power, etc.
While examining this problem, I noticed an interesting property:
Every time an edge is added, either the number of minimal cycles increases by 1, or the number of disjoint components decreases by one.
Every time an edge is removed, the reverse happens.
This property is likely well known in graph theory and I'm re-inventing the wheel. I'm sure I could look it up if I knew the proper mathematical name for what I'm calling a "minimal cycle." It would likely be phrased as something like:
Count of vertices = Count of edges + Count of disjoint components - Count of minimal cycles
I wanted to pose a puzzle that would lead people to this property.
Unfortunately, there's a very obvious brute force algorithm (flood filling the entire graph every time a modification occurs) which does not utilize this property. In translating from "programming" to "pure math," I attempted to rewrite the problem so that "too slow" would become "infinitely slow," but I didn't account for ways to reduce the space to finite, nor that it was possible to ignore cycles entirely by processing all additions after all removals.