Redundant Connection
Module 23 · Graphs
Problem
A tree with n nodes originally had exactly n - 1 edges (no cycles).
One EXTRA edge was added, creating exactly one cycle. Given the list of
n edges (as [u, v] pairs, in the order they were added), find the
one edge that, if removed, restores the graph to a tree. If multiple
such edges could work, return the one that appears LAST in the input.
(LeetCode 684.)
Examples
Example 1
edges = [[1,2],[1,3],[2,3]]Output[2,3]Example 2
edges = [[1,2],[2,3],[3,4],[1,4],[1,5]]Output[1,4]Constraints
nnodes, exactlynedges (one more than a tree needs), no self-loops or duplicate edges.
Attempt it first
Since the input is a TREE plus exactly one extra edge, exactly one edge
in the list — when added — will connect two nodes that were ALREADY
connected by the edges before it. That edge is both the cause of the
cycle and the answer. Before opening anything, think about how you'd
detect, incrementally, edge by edge in input order, "were these two
endpoints already connected before this edge was added" — and why
Union-Find's find operation answers exactly that question in near-O(1)
per edge, without needing a separate detection pass.