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.
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.
If the graph and bridge tree is needed to be directed. We have to find all the SCCs and connect LCC to SCC then from one SCC we connect the others right ?
Thank you so much. Will try this approach.
UPD it worked thankyou so much learned a good concept.
Can you suggest some problems which make use of bridge tree.
Thanks again
Problem H here
178B3
652E
1000E
700C
Congrats on reaching cyan :)
Thanks :)