A random edge *e* is added to a graph. It happens to not be a bridge edge. Let *C* be the connected component of the endpoints of *e*.

Given the list *L* of all the bridge edges of *C* (before *e* was added), which is the fastest algorithm to find which edges in *L* are still bridge edges after the insertion of *e*?

# Best How To :

If you allow preprocessing, there is a fast method: Construct the bridge-block forest, whose vertices are 2-connected components, and whose edges are bridges. (It's a tree if the graph is connected.) When you add an edge, if this connects points in the same 2-connected component, nothing happens. If you connect points in different 2-connected components that were in different connected components of the bridge-block forest, then the new edge is a bridge (which you assume doesn't happen). If you connect two 2-connected components in the same connected component, then find the unique path of bridges between those 2-connected components. Those are no longer bridges, and all of the 2-connected components along the path are contracted to a new 2-connected component. Any bridge that is not along this path is still a bridge.

There is a comment stating that you eliminate at most one bridge. This is incorrect. You can connect any two points in the bridge-block forest, including points of arbitrary distance. Adding such an edge will eliminate arbitrarily many edges.

In your comments, you mention deleting edges. This might do nothing, but if you delete a non-bridge e, it might cause the 2-connected component C containing e to break into an arbitrarily long path, so you need to recompute the 2-connected components within C and replace C by this path of 2-connected components. The bridges connecting C to other 2-connected components become bridges connecting the new 2-connected components C_!, ..., C_k to the neighbors of C.