Redundant Connection

**Problem Statement:** Given the required input arguments, write an efficient algorithm to solve the **Redundant Connection** problem. Implement the required logic as specified by standard definitions for this classic algorithmic challenge. **Hint / Expected Approach:** Union-Find: detect edge forming a cycle **Edge Cases to Consider:** - (1) Cycle at start - (2) Chain of nodes - (3) Multiple valid answers (return last)

Examples

Example 1

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

Output: [2,3]

Explanation: Cycle: 1-2-3-1

Example 2

Input: [[1,2],[2,3],[3,4],[1,4],[1,5]]

Output: [1,4]

Explanation: Cycle 1-2-3-4-1

Example 3

Input: [[1,2]]

Output: N/A (min 3 nodes)

Explanation: Edge case

Constraints

▪2 <= vertices <= 1000
▪0 <= edges <= 5000
▪Avoid infinite cycles during depth traversal

Watch Out For Edge Cases

▪Cycle at start
▪Chain of nodes
▪Multiple valid answers (return last)

Frequently Asked At

AmazonGoogleMicrosoft

Back to Arena

medium

Graph