Please, try EDU on Codeforces! New educational section with videos, subtitles, texts, and problems. ×

Mikemirzyanov1's blog

By Mikemirzyanov1, history, 4 months ago, In English,

Can someone share the details to construct the bridge tree provided we have the bridges? I have already seen the quora link for bridge tree but cannot understand as it uses edge list representation of graph which I don't know.

I know how to find bridges and need to perform dfs on the bridge tree, but how to construct it. Someone please help.

 
 
 
 
  • Vote: I like it
  • +8
  • Vote: I do not like it

»
4 months ago, # |
  Vote: I like it +5 Vote: I do not like it

1) Remove these bridges from the graph

2) Find connected components using the remaining (non bridge) edges using dsu or dfs or whatever you like.

3) Treat each connected component as a node, and for each bridge add an edge between the two components that it connects.