A tree of n nodes (labeled 1..n) had one extra edge added. Given the edge list, return an edge that can be removed so the graph becomes a tree again; if several work, return the one that appears last in the input.
Union the endpoints of each edge. The first edge whose endpoints already share a root connects two nodes that were already connected: that edge is redundant.
1function findRedundantConnection(edges: number[][]): number[] {2const parent = Array.from({ length: edges.length + 1 }, (_, i) => i);3const find = (x: number): number => (parent[x] === x ? x : (parent[x] = find(parent[x])));4for (const [u, v] of edges) {5const a = find(u), b = find(v);6if (a === b) return [u, v];7parent[a] = b;8}9return [];10}
Every node is its own set.
Space: play/pause · ←/→: step