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

Revision en1, by ritik_patel05, 2020-10-22 22:11:16

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)

Graph0

It's Bridge Tree would be,

Graph1

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.

Full Code:

Code Link

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

  1. 652E , Submission using Above implementation.
  2. H-Bridges, Submission using above implementation.
  3. 178-B3
  4. Sherlock and Queries on the Graph- HackerRank
  5. 1000-E
  6. 732-F
  7. 6044-Unique Path-ICPC Live Archive
  8. 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!

Tags #bridges, bridge-tree, 2-edge-connectivity

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English ritik_patel05 2020-10-22 22:11:16 8074 Initial revision (published)