Quickly identify changes in connectivity Given an undirected graph with at least one path connecting $u, v$, and a sequence of edges to be removed: $e_1, e_2, \dots$, I would like to quickly identify the point at which $u$ will be separated from $v$. Clearly this could be done by doing a full path search after each removed edge, but this is very expensive.
Is there a faster algorithm? (This is this question which asks about a related but more general and difficult situation, but it has gone unanswered.)
You can work your way backwards. Suppose the edges being removed are $e_1,\ldots,e_\ell$, and the rest of the edges form a set $E$. Start by determining the connected components induced by $E$, using a disjoint sets data structure. Now add the edges $e_\ell,\ldots,e_1$ in that order, updating the disjoint sets data structure, until $u$ and $v$ belong to the same connected component. The last edge encountered in this way is the one you seek.