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.
- 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)
- 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:
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!