The problem. A tree with n vertices, labelled 1 to n, had one extra edge added, so now there are n edges and exactly one cycle. Given the edges in order, return an edge you can remove to get a tree back. If several would work, return the one that appears last in the input.
edges = [[1,2],[1,3],[2,3]] -> [2,3]
edges = [[1,2],[2,3],[3,4],[1,4],[1,5]] -> [1,4]Some questions are about groups that merge: which vertices are connected so far, are these two in the same group, join these two groups. A Union-Find (also called a disjoint set union) answers them almost instantly, even while edges keep arriving — no search needed.
Each group is stored as a little tree in one array, parent. Every vertex points at its parent, and the root — the vertex that points at itself — names the group. Two operations:
x to the root. Two vertices are in the same group exactly when they have the same root.
Two small tricks keep the trees flat. Union by size: hang the smaller tree under the bigger one, so trees grow wide, not tall. Path halving: while find climbs, point each vertex at its grandparent, so the next climb is shorter. With both, each operation takes O(α(n)) — α is the inverse Ackermann function, which is below 5 for any input that fits in a computer. In practice: constant time.
Here, the question is exactly were these two already connected? Add the edges in order; the first edge whose two ends already share a root closes the cycle.
Before adding edge u - v, run a DFS to see whether u can already reach v. If it can, this edge makes a second route between them: it's the redundant one.
function findRedundantConnection(edges) { const adj = Array.from({ length: edges.length + 1 }, () => []); const connected = (from, to) => { // is there already a path from -> to? const seen = new Set([from]); const stack = [from]; while (stack.length > 0) { const x = stack.pop(); if (x === to) return true; for (const y of adj[x]) { if (!seen.has(y)) { seen.add(y); stack.push(y); } } } return false; }; for (const [u, v] of edges) { if (connected(u, v)) return [u, v]; // a second route: this edge closes the cycle adj[u].push(v); adj[v].push(u); } return [];}Time O(n²), space O(n). Each of the n edges may search the whole graph built so far. The same question — already connected? — is answered from scratch every time.
Start with every vertex in its own group. For each edge, find the roots of both ends. Different roots: union the groups. The same root: the ends were already connected, so return this edge.
Groups merge as edges arrive; watch the parent pointers form trees. The edge whose ends share a root is the answer.
function findRedundantConnection(edges) { const n = edges.length; const parent = Array.from({ length: n + 1 }, (_, i) => i); // everyone starts in their own group const size = new Array(n + 1).fill(1); const find = (x) => { while (parent[x] !== x) { parent[x] = parent[parent[x]]; // path halving: skip a level on the way up x = parent[x]; } return x; // the root names the group }; for (const [u, v] of edges) { let a = find(u), b = find(v); if (a === b) return [u, v]; // already in one group: this edge closes a cycle if (size[a] < size[b]) [a, b] = [b, a]; parent[b] = a; // hang the smaller tree under the bigger one size[a] += size[b]; } return [];}Time O(n · α(n)), space O(n). Each edge does two finds and at most one union, each practically constant. Why is the first edge that closes a cycle also the last one on it in the input? Every other edge of the cycle was added before it without closing anything.
Union-Find wins whenever edges arrive one at a time and the question is connected yet? A DFS has to search again after every edge; Union-Find just remembers the groups.
[[1,2],[1,3],[2,3]] returns [2,3], the last edge of the triangle.find can walk a chain of n vertices every time and the whole thing becomes O(n²).n + 1 and ignore index 0.