Live Batches
Masterclasses
Menu
Free Courses
Account
Login / Sign Up

Redundant Connection

Medium Acceptance 68.71% Points 30

You are given an undirected graph that started as a tree with one extra edge added. Your task is to return the redundant edge whose removal makes the graph a tree again.

The redundant edge is the edge that creates a cycle in the graph.

Return the edge whose removal restores the tree structure.

Examples
Example 1

image Input: edges = [[1,2],[1,3],[2,3]]
Output: [2,3]
Explanation: Removing edge [2,3] restores the tree.

Example 2

image Input: edges = [[1,2],[2,3],[3,4],[1,4],[1,5]]
Output: [1,4]
Explanation: Removing edge [1,4] removes the cycle.

Example 3

image Input: edges = [[1,2],[2,3],[3,1]]
Output: [3,1]
Explanation: The last edge completes the cycle.

Constraints
    • 2 = Number of nodes = 1000
    • Number of edges = Number of nodes
    • 1 = u, v = Number of nodes
Topics
Graph
Companies
ZScaler Mastercard
Added 15 Aug 2026 68.71% acceptance
Ln 1, Col 1Sign in to save your code
3 3
1 2
1 3
2 3
2 3