Bridge Tree(2-edge connected) decomposition of graph[Tutorial and Problems]

Hello, codeforces!

I don't know how helpful will this be to anyone, but I thought it would be nice to share it. Before reading this blog, you should be familiar with the concept of Bridges in a graph.

What it can do

1. Find minimum number of edges to add in a graph, so that there are no bridges.
2. Add a single edge to minimize the number of bridges in a graph.
3. Given a graph, and queries in from A B C D: For the current query add an edge between nodes numbered A and B(note that this operation is temporary and only for the current query). Now, output the maximum number of bridge edges occuring on any path between C and D.

What is Bridge Tree of a graph?

One of the formal terms often used to describe Bridge tree is decomposing graph into 2-edge connected components and making a tree of it.

2-edge connected component in simple terms is a set of vertices grouped together into a component, such that if we remove any edge from that component, that component still remains connected. In short, it's a component which doesn't have any bridges in it.

So, how can we make bridge tree of a graph?

In Bridge Tree we will have => Nodes as:-> 2-edge connected components. and, edges as:-> Bridge connecting two different components.

Example, Consider we have a graph. (Red line edge is a bridge)

It's Bridge Tree would be,

How to implement

1. Find bridges in the graph and mark them.

1. Remove the bridge from the graph.
2. Run dfs/dsu or bfs whichever way you prefer to group one components and give vertices the component id in which they belong. (Note: Remove bridge means: while traversing make sure not to cross the bridge, so we can group vertices of one component)

1. Traverse every edge, if it is a bridge, connect the two components via an edge.

Alternative Implementation:

There is also alternative implementation using dfs and queues(bfs) mentioned in this blog which is also on this same topic. Link

Honestly, i think using just dfs to find components is intuitively to me and easy to code. You can use any approach you like.

Full Code:

Code Link

Thanks to

I already found this blog about Bridge tree on quora(Link) but I found implementation hard to interpret. Also, thanks to Algorithms Live Channel on Youtube which really helped me to clear concepts on Bridge Finding and forming 2 edge connected component tree of a graph and biconnected components in general.

Problems

If you have any doubts regarding explanation, you can ask in comments. Also, if you have solved problems related to it, please share it here, I will update the Problems section.

Have a great day!