Process edges in order with Union-Find. The first edge whose endpoints are already connected is the redundant one.

Redundant Connection

medium

Acceptance: 53%

GraphsUnion Find

A graph was originally a tree on n nodes (labeled 1 to n) but had one extra edge added, creating exactly one cycle. Identify the extra edge whose removal restores the tree. When multiple edges qualify, return the one appearing last in the input.

Examples

Example 1:

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

Output:[3,1]

Explanation: Removing [3,1] (the last edge forming the cycle) restores a valid tree.

Example 2:

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

Output:[2,3]

Explanation: Edge [2,3] is the last edge that closes the cycle 1-2-3.

Hints

1234567

import java.util.*;

public class Main {
    public static void main(String[] args) {
        // Write your solution here
    }
}

import java.util.*;

public class Main {
    public static void main(String[] args) {
        // Write your solution here
    }
}

Redundant Connection

Examples

Hints

Related Problems