How do you approach Redundant Connection?

Process edges in order with union-find.

What are common mistakes on Redundant Connection?

Building the adjacency list in one direction on an undirected graph. Assuming the graph is connected. Most inputs allow several components, and one traversal from node 0 misses the rest. Ignoring self-loops and parallel edges when the constraints allow them.

gitGood.dev

← Back to problems

Redundant Connection

MediumAlgorithms

Description

A tree with n nodes (labeled 1 to n) had one extra edge added, creating exactly one cycle. You are given the resulting edges array.

Return the edge that can be removed so that the result is a tree of n nodes. If there are multiple answers, return the edge that occurs last in the input.

Example 1

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

Output: [2,3]

Explanation: Removing [2,3] leaves a tree.

Example 2

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

Output: [1,4]

Explanation: [1,4] closes the cycle 1-2-3-4-1.

Constraints

- n == edges.length - 3 <= n <= 1000 - edges[i] = [a, b], 1 <= a < b <= n

Redundant Connection: approach, complexity and pitfalls

A medium graphs problem, graded against 6 test cases (4 of them hidden).

The pattern: Graphs

Nodes and edges - traversal, connectivity, cycles, and shortest paths.

Reach for it when you see: Explicit edges, a grid treated as a graph, or dependencies between items.

If you are stuck

Show the 2-step hint ladder

Process edges in order with union-find.
The first edge whose endpoints already share a root is the one closing the cycle.

The optimal approach

Show the approach: The approach

Union-Find. Scan edges left to right. For each edge, if the two endpoints already belong to the same set, this edge created the cycle - return it. Because we scan in order, this is naturally the last such edge.

Time: O(n·α(n)). Space: O(n).

The full reference solution in every supported language stays in the editor above - reveal it there once you have had a real attempt.

Common Graphs mistakes

These apply to the pattern as a whole, not just this problem.

Building the adjacency list in one direction on an undirected graph.
Assuming the graph is connected. Most inputs allow several components, and one traversal from node 0 misses the rest.
Ignoring self-loops and parallel edges when the constraints allow them.