Reverse-Delete MST — Delete Max Edge if Safe

Algorithm

Sort edges by weight descending. For each edge (in that order), try removing. Check connectivity. Keep if disconnects, delete if not.

Advertisement

O(E × (V+E)) with naive connectivity check. O(E × α(V) × log(V)) with smart DSU + link-cut trees.

Advertisement

Cycle property: max-weight edge on any cycle is not in MST. Reverse-delete finds exactly these.

Kruskal (add min if no cycle) vs reverse-delete (remove max if not bridge). Both O(E log V) with proper DS.