Mikemirzyanov1's blog

By Mikemirzyanov1, history, 5 years 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

»
5 years 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.