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

- Find minimum number of edges to add in a graph, so that there are no bridges.
- Add a single edge to minimize the number of bridges in a graph.
- 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

- Find bridges in the graph and mark them.

**Code**

- Remove the bridge from the graph.
- 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**

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

## Full Code:

**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

- 652E , Submission using Above implementation.
- H-Bridges, Submission using above implementation.
- 178-B3
- Sherlock and Queries on the Graph- HackerRank
- 1000-E
- 732-F
- 6044-Unique Path-ICPC Live Archive
- 700-C

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!