Command Palette

Search for a command to run...

Hectal
Problem 23.2 · Cycle DetectionMedium

Redundant Connection

PatternUnion-FindGraph DFS and Flood Fill

What it teaches: The first edge that joins two already-connected nodes is the one that closed the cycle.

Practise it on judges as “Redundant Connection”.

The problem

A tree of n nodes (1..n) had one extra edge added. Return an edge that can be removed so the result is a tree; if several work, return the one that appears last in the input.

Example 1

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

Constraints

  • 3 ≤ n ≤ 1000

Pattern clues in the wording

  • → Exactly one extra edge in a tree

These clues point to Union-Find: Keep each group as a tree with a root; find the root to test membership and link roots to merge groups.

Stuck? Take one hint at a time

Solution.java · starter
class Solution {
    public int[] findRedundantConnection(int[][] edges) {
        return new int[0];
    }
}

Write your solution locally or in your editor for now. The in-browser runner (Java first, then Python, C++ and more) will run these tests right here.

Test cases

#InputExpected
1
edges = [[1,2],[1,3],[2,3]]
[2,3]
2
edges = [[1,2],[2,3],[3,4],[1,4],[1,5]]
[1,4]

From slow to fast

Approaches

1. Union-find · O(n α(n))
1

Union-find

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

Union edges in order; return the first edge with both ends in the same set. It's the last edge of the only cycle in input order.

Approach 1
class Solution {
    private int[] parent;

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

    private int find(int x) {
        while (parent[x] != x) { parent[x] = parent[parent[x]]; x = parent[x]; }
        return x;
    }
}

Verdict: Exactly the cycle check from the lesson.

Before you submit

Edge cases and common mistakes

Test these inputs

  • Cycle through every node
  • Extra edge listed last

Mistakes people make

  • Returning the first edge of the cycle instead of the one that closes it.

Interview

Follow-up questions

What changes for a directed graph (Redundant Connection II)?