Redundant Connection: the idea to remember.

The core insight

Process edges in order, joining components until an edge connects vertices already in the same component.

Why it works

A tree contains no cycle; the first edge inside one existing component closes the unique cycle.

The mistake to avoid

Check roots before joining them, and return the actual redundant edge rather than component identifiers.

Commented Java solution

Use java.util.* imports and a surrounding solution class. Tree snippets assume the standard TreeNode definition; linked lists use ListNode and Clone Graph uses a Node with val and neighbors; Copy Random List uses Node with val, next and random. Read the input assumptions above.

// Java reference adapted from neetcode-gh/leetcode (MIT).
// Process edges in order, joining components until an edge connects vertices already in the same component.
int[] parent;

public int[] findRedundantConnection(int[][] edges) {
    parent = new int[edges.length];
    for (int i = 0; i < edges.length; i++) parent[i] = i + 1;

    for (int[] edge : edges) {
        if (find(edge[0]) == find(edge[1])) return edge; else union(
            edge[0],
            edge[1]
        );
    }

    return new int[2];
}

public int find(int x) {
    if (x == parent[x - 1]) return x;
    return find(parent[x - 1]);
}

public void union(int x, int y) {
    parent[find(y) - 1] = find(x);
}

Java reference adapted from neetcode-gh/leetcode · MIT license

Make the next connection