The Widest Road Trip — Solution & Editorial

Back to the Problem

Add edges in decreasing width into a union-find; the width that first connects 1 and N is the answer (equivalently: the min edge on the 1–N path in a MAXIMUM spanning tree, or binary search + BFS).

Complexity: O(M log M α(N))