← Algorithmic Patterns
mediumGraphs

Redundant Connection

An undirected tree on vertices 1 through n has one extra edge. Return the edge that creates a cycle when edges are added in input order.

LeetCode ↗

Work through the cases

3 examples

Input notation

One edge u v per line. The graph has exactly one cycle.

Expected result

The redundant edge as u v in its input orientation.
Case 1

Input

1 2
1 3
2 3

Expected output

2 3
Case 2

Input

1 2
2 3
3 4
1 4

Expected output

1 4
Case 3

Input

1 2
2 3
3 1

Expected output

3 1

These notes use simplified input/output notation. The linked platform defines the method signature and judge format.

FROM IDEA TO IMPLEMENTATION

Understand the approach.

Compare the documented approaches below. Brute force, better, and optimal versions appear where available; a direct exercise may need only one approach.

An undirected tree plus one extra edge; delete the last extra edge in the input. Finding the cycle and ranking edges is heavier than needed. Union-Find the edges in order. The first pair already in one component is the redundant edge.

According to the problem description, we need to find an edge that can be removed so that the remaining part is a tree with n nodes. We can traverse each edge and determine whether the two nodes of this edge are in the same connected component. If they are in the same connected component, it means this edge is redundant and can be removed, so we directly return this edge. Otherwise, we merge the two nodes connected by this edge into the same connected component.

The time complexity is O(n log n), and the space complexity is O(n). Here, n is the number of edges.

class Solution {
    private int[] p;

    public int[] findRedundantConnection(int[][] edges) {
        int n = edges.length;
        p = new int[n];
        for (int i = 0; i < n; ++i) {
            p[i] = i;
        }
        for (int i = 0;; ++i) {
            int pa = find(edges[i][0] - 1);
            int pb = find(edges[i][1] - 1);
            if (pa == pb) {
                return edges[i];
            }
            p[pa] = pb;
        }
    }

    private int find(int x) {
        if (p[x] != x) {
            p[x] = find(p[x]);
        }
        return p[x];
    }
}

Reference code. Platform solutions may use supplied node types, imports, or collection libraries; foundational examples are complete programs.

Solutions adapted from Doocs / LeetCode contributors, licensed under CC BY-SA 4.0. Formatting changed; TypeScript versions converted to JavaScript. Supplemental implementations and approach notes added. Adapted solution material is available under the same license.