Problem statement

A tree of n nodes (labelled 1..n) had one extra edge added, creating exactly one cycle. Given the resulting edge list, return the edge that can be removed to restore a tree. If several answers exist, return the one that occurs last in the input.

Example 1

Input: edges = [[1,2],[1,3],[2,3]]
Output: [2,3]

Example 2

Input: edges = [[1,2],[2,3],[3,4],[1,4],[1,5]]
Output: [1,4]

Constraints

• 3 <= n <= 15
• edges.length == n
• The input is a tree plus one extra edge.

Hints for Redundant Connection

1. Hint 1

   Union-Find: process edges in order, uniting endpoints.

2. Hint 2

   The first edge whose endpoints are already connected is the answer.

How to solve Redundant Connection

A tree on n nodes has exactly n - 1 edges and no cycle. Adding one more edge creates exactly one cycle, and the culprit is the edge that first joins two nodes already connected. Union-Find answers "already connected?" in near-constant time, so a single pass over the edges finds it.

Approach

1. Start with every node in its own set.
2. Process the edges in input order. For each, find the representative of both endpoints.
3. If the representatives differ, the edge joins two separate pieces — unite them and move on.
4. If they are the same, both endpoints were already connected, so this edge closes the cycle: return it.
5. Exactly one edge triggers this, because the input is a tree plus one edge.

Why it works

Scanning in order, the structure stays a forest as long as each edge joins distinct components. The first edge whose endpoints already share a component must create a cycle — a path between them already exists. And it is automatically the answer the problem wants: if several edges lie on the cycle, the one appearing latest in the input is precisely the one that closes it, since the earlier ones were still joining separate pieces when they were processed.

Complexity

• Time — O(n α(n))
• Space — O(n)

Pitfalls

• Nodes are labelled from 1, so size the parent array n + 1.
• Compare the roots, not the raw labels — two nodes can be connected without pointing at each other.
• Return the edge in its original orientation, exactly as it appeared in the input.
• Process edges strictly in input order; sorting them destroys the "occurs last" guarantee.

Reference solution

Python

from typing import List

def findRedundantConnection(edges: List[List[int]]) -> List[int]:
    n = len(edges)
    parent = list(range(n + 1))

    def find(x):
        while parent[x] != x:
            parent[x] = parent[parent[x]]
            x = parent[x]
        return x

    for a, b in edges:
        ra, rb = find(a), find(b)
        if ra == rb:
            return [a, b]
        parent[ra] = rb
    return []

Java

public static int[] findRedundantConnection(int[][] edges) {
    int n = edges.length;
    int[] parent = new int[n + 1];
    for (int i = 0; i <= n; i++) parent[i] = i;
    for (int[] e : edges) {
        int a = findRoot(parent, e[0]);
        int b = findRoot(parent, e[1]);
        if (a == b) return new int[]{e[0], e[1]};
        parent[a] = b;
    }
    return new int[0];
}

private static int findRoot(int[] parent, int x) {
    while (parent[x] != x) {
        parent[x] = parent[parent[x]];
        x = parent[x];
    }
    return x;
}

C++

int findRootRC(vector<int>& parent, int x) {
    while (parent[x] != x) {
        parent[x] = parent[parent[x]];
        x = parent[x];
    }
    return x;
}

vector<int> findRedundantConnection(vector<vector<int>>& edges) {
    int n = (int) edges.size();
    vector<int> parent(n + 1);
    for (int i = 0; i <= n; i++) parent[i] = i;
    for (const auto& e : edges) {
        int a = findRootRC(parent, e[0]);
        int b = findRootRC(parent, e[1]);
        if (a == b) return vector<int>{e[0], e[1]};
        parent[a] = b;
    }
    return vector<int>();
}

JavaScript

var findRedundantConnection = function(edges) {
    const n = edges.length;
    const parent = [];
    for (let i = 0; i <= n; i++) parent.push(i);
    function find(x) {
        while (parent[x] !== x) {
            parent[x] = parent[parent[x]];
            x = parent[x];
        }
        return x;
    }
    for (const e of edges) {
        const ra = find(e[0]), rb = find(e[1]);
        if (ra === rb) return [e[0], e[1]];
        parent[ra] = rb;
    }
    return [];
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More graph problems

• Minimize Maximum Component Cost Medium
• Minimum Time for K Connected Components Medium
• Power Grid Maintenance Medium
• Minimum Time to Reach Destination in Directed Graph Medium
• Unit Conversion I Medium
• Digit Operations to Make Two Integers Equal Medium