Is there a data structure to keep track of the connected components of a dynamic graph, when the graph might by changing by deleting edges of the graph?Let $G$ be an undirected graph.  I have two operations I'd like to be able to perform:Delete$(u,v)$: delete the edge $(u,v)$ from the graph.SameComponent$(u,v)$: returns true or false according to whether $u,v$ are in the same connected componentIs there a data structure that allows me to perform both operations relatively efficiently?The naive data structure is simply to store the graph in adjacency list representation, and answer SameComponent$(u,v)$ queries by doing a depth-first search from $u$ to see if $v$ is reachable.  However, that makes the SameComponent operation take linear time, and it feels like it is re-doing a lot of work, so maybe there is a more efficient algorithm.  Is there a data structure where both operations can be done in sub-linear running time?One way to think about it is that I am basically asking for the dual of the Union-Find data structure.  The Union-Find data structure offers two operations:Union$(u,v)$: add an edge $(u,v)$ to the graph.Find$(v)$: return an identifier for the connected component containing $v$ (e.g., a vertex that acts as the representative for the connected component containing $v$).You could think of this question as asking for a Split-Find data structure, which should support two operations:Split$(u,v)$: delete the edge $(u,v)$ from the graph.Find$(v)$: return an identifier for the connected component containing $v$ (e.g., a vertex that acts as the representative for the connected component containing $v$).As we know, there is an efficient Union-Find data structure.  The apparent symmetry between Union-Find and Split-Find makes me wonder whether there is also an efficient Split-Find data structure, too.Of course, if we had an efficient Split-Find data structure, we could answer the original problem: Delete$(u,v)$ would be implemented by calling Split$(u,v)$, and SameComponent$(u,v)$ would be implemented by testing whether Find$(u) = $ Find$(v)$.So, is there an efficient Split-Find data structure?
Split-Find: maintaining dynamic graph connectivity information, under edge deletion
graphs;data structures;union find
It sounds like you're looking for decremental connectivity. The fastest result I could find was Wulff-Nilson's Faster deterministic fully-dynamic graph connectivity, which supports updates (edge insertions/deletions) in $O(\log^2 n/ \log \log n)$ amortized time and connectivity queries in $O(\log n/ \log \log n)$ worst-case time, where $n$ is the number of vertices of the graph.