### ritik_patel05's blog

By ritik_patel05, history, 5 weeks ago,

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.
Code
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)
Code
1. Traverse every edge, if it is a bridge, connect the two components via an edge.
Code

#### 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.

Code

## 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!

• +13