Redundant Connection

The problem

Given `edges` for a graph that started as a tree on `n` nodes (labelled `1` to `n`) and then had one extra edge added, return an edge that can be removed to make it a tree again. If more than one edge could be removed, return the one that appears last in `edges`.

`edges = [[1,2],[1,3],[3,4],[2,4]]` returns `[2,4]`. `edges = [[1,2],[1,3],[1,4],[3,4],[4,5]]` returns `[3,4]`.

The approach

`graph-valid-tree` already found the shape of this: walk `edges` once, union each pair's roots, and the moment an edge connects two nodes that already share a root, that edge is the cycle. There, that moment just returned `false`. Here, the edge itself is the answer, so the DSU loop returns it directly in place of the boolean.

Only one such edge exists in the whole input — the graph is a tree (`n - 1` edges) plus exactly one more — so there's no need to keep scanning for a 'last' one or compare candidates. The first (and only) edge whose endpoints already share a root when it's processed in input order is the one being asked for, which is automatically the last-appearing answer the problem wants, since it's the only answer.

Nodes are labelled `1` to `n`, not `0` to `n - 1` like the rest of the graph entries, so `parent` is sized `n + 1` and left index `0` unused rather than shifting every id down by one.

The solution

class Solution {
    /**
     * @param {number[][]} edges
     * @return {number[]}
     */
    findRedundantConnection(edges) {
        const n = edges.length;
        const parent = Array.from({ length: n + 1 }, (_, i) => i);

        const find = (x) => {
            while (parent[x] !== x) {
                parent[x] = parent[parent[x]];
                x = parent[x];
            }
            return x;
        };

        for (const [a, b] of edges) {
            const rootA = find(a);
            const rootB = find(b);
            if (rootA === rootB) return [a, b];
            parent[rootA] = rootB;
        }
    }
}

Time O(n α(n))Space O(n)