Redundant Connection

mediumGraphs: Topological Sort & Union-Find61 stepsJava · Python · C++

A tree had one extra edge added, creating exactly one cycle. Add edges one by one with union-find; the first edge whose two endpoints are already connected closes the cycle and is the answer.

▶ Watch the animated trace

Traced input: edges = [[1, 2], [2, 3], [3, 4], [1, 4], [1, 5]] → [1, 4]. Original problem: neetcode.io/problems/redundant-connection

Complexity

BestO(n α(n))

AverageO(n α(n))

WorstO(n α(n))

SpaceO(n)

One find/union per edge.

Key idea

Two nodes already in the same set are connected by some path.
Adding an edge between them creates a cycle.
Processing edges in order returns the last such edge in the input, as required, because there's exactly one.

Common mistakes

Nodes are 1-indexed; size parent as n + 1.
DFS for every edge is O(n²).

Solution

Java

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

int root(int[] parent, int x) {
    while (parent[x] != x) {
        parent[x] = parent[parent[x]];
        x = parent[x];
    }
    return x;
}

Python

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

    def root(x: int) -> int:
        while parent[x] != x:
            parent[x] = parent[parent[x]]
            x = parent[x]
        return x

    for u, v in edges:
        a, b = root(u), root(v)
        if a == b:
            return [u, v]
        parent[a] = b
    return []

C++

int root(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) {
    vector<int> parent(edges.size() + 1);
    iota(parent.begin(), parent.end(), 0);
    for (auto& e : edges) {
        int a = root(parent, e[0]), b = root(parent, e[1]);
        if (a == b) {
            return e;
        }
        parent[a] = b;
    }
    return {};
}

Edge cases

Each one has its own trace in the interactive view.

Case	Input	Answer
Triangle The third edge closes the triangle.	`edges = [[1, 2], [1, 3], [2, 3]]`	`[2, 3]`
Cycle closed early A duplicate edge is a cycle of length 2.	`edges = [[1, 2], [2, 1], [1, 3]]`	`[2, 1]`