Bridge tree
Contract each 2-edge-connected component. Bridges become tree edges. Result: tree of bridges.
Advertisement
Construction
Tarjan bridge algo + DSU. O(V+E).
Advertisement
Applications
Network reliability. Every bridge = critical connection. Tree structure aids efficient queries.
Path queries
Number of bridges on path between u, v = length of path in bridge tree. LCA-based query in O(log V).