0
$\begingroup$

I have an undirected graph which may have 2 edges that connect the same pair of nodes.

A group of nodes that don't need any bridges to go from a node to another should be merged into one node in a new tree. That tree should contains such nodes and all bridges in the original graph.

What is the algorithm to solve this problem, given that the numbers of nodes and edges in the graph are smaller than 2*10^5?

$\endgroup$
0
$\begingroup$

What you want is to find the 2-edge-connected components of your graph. When you have a simple graph, you can do that by finding all bridges in your graph in linear time, delete them and find the connected components in the resulting graph (every connected component corresponds to a vertex in the final graph).

Now to ensure that this works also in your case where you can have multiple edges between two vertices you can simply ignore when the above algorithm finds an incorrect bridge (u,v), where u and v are connected by multiple edges. Don't delete this edge from your graph when this happens. To detect when this happens you can first find all duplicate edges (either by sorting all edges first or using some hashing method), store those edges in a container where they can efficiently be searched (hashing or binary search) and then for every detected bridge, test if it is in that container.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.