Redundant Connection
Problem Statement
You are given an undirected graph that started as a tree with n nodes labelled 1 to n. Then one extra edge was added between two different nodes that were not already directly connected.
Return the edge that can be removed so the remaining graph is again a tree. If more than one edge could be removed, return the one that appears last in the input.
Input
An edge list edges for an undirected graph whose node labels are 1..n and whose length is n.
Output
The redundant edge [u, v] whose removal restores a valid tree.
Constraints
- •
n == edges.length - •
3 <= n <= 1000 - •
edges[i].length == 2 - •
1 <= ai < bi <= n - •
ai != bi - •
There are no repeated edges. - •
The input graph is connected and contains exactly one cycle.
Examples
Example 1
edges = [[1,2],[1,3],[2,3]]
[2,3]Example 2
edges = [[1,2],[2,3],[3,4],[1,4],[1,5]]
[1,4]Learning Objectives
- Recognise that a tree plus one edge creates exactly one cycle.
- Use Union-Find to identify the first edge whose endpoints were already connected by earlier edges.
- Explain why processing edges in input order satisfies the last removable edge requirement for the single-cycle input model.
- Separate cycle detection from path recovery: the redundant edge is enough, not the full cycle.
Intuition
Imagine building the original tree back from left to right. Every normal tree edge connects two components that were previously separate. The extra edge is different: by the time it appears, its two endpoints already have a path between them through earlier edges. Adding it would create the only cycle.
That is exactly what Union-Find tracks. Each set represents one connected component formed by edges processed so far. If u and v have different roots, the edge is useful and we merge the sets. If they have the same root, the edge is redundant because a path already exists without it.
The input guarantee matters. Since the graph is a tree plus one edge, there is one cycle. The edge returned by the left-to-right Union-Find scan is the cycle edge that appears after the rest of its connecting path has already appeared, which is the required removable edge under LeetCode's ordering rule.
Common mistakes
- ×Allocating Union-Find for **edges.length** instead of **edges.length + 1** even though labels start at 1.
- ×Returning the first edge that shares a direct endpoint with another edge. Sharing a vertex is normal; sharing a connected component is the cycle signal.
- ×Unioning before checking whether the endpoints already have the same root.
- ×Using DFS from scratch for every edge in code, which is correct but noisier and slower than the intended Union-Find pattern.
- ×Forgetting path compression or rank, then describing near-constant time without actually implementing it.
Algorithm Explanation
- Create a Union-Find structure sized for labels 1..n.
- Process edges in the given order.
- For edge [u, v], compare roots. If the roots match, u and v were already connected, so this edge closes the cycle and is the answer.
- Otherwise union the two roots and continue.
- The problem guarantees an answer, so the loop will return from the cycle-closing edge.
A DFS-per-edge alternative can test whether u already reaches v before adding the edge, but it rebuilds or repeatedly searches adjacency. Union-Find is the cleaner optimal solution for an undirected incremental connectivity question.
Solutions
Solution: Union-Find with path compression and rank
Use this whenever an undirected graph is built edge by edge and the question is whether the next edge connects vertices that are already connected. It is the intended optimal pattern here and avoids repeated graph searches.
Maintain connected components for the prefix of edges already accepted. A successful edge merges two components. A failing edge has both endpoints in the same component, meaning the earlier accepted edges already contain a path between them; return that edge immediately.
Step-by-step
- Initialise parent[i] = i for labels 1..n and keep a rank array.
- For each edge, find both roots with path compression.
- If the roots match, return the edge because adding it would close a cycle.
- Otherwise attach the shallower tree under the deeper one.
- The guaranteed single extra edge ensures the method returns during the scan.
O(N · α(N))
O(N)
N is the number of edges and nodes; α is effectively constant for interview-sized inputs.
Java implementation
Dry Run
Sample input
Union-Find trace for edges = [[1,2],[2,3],[3,4],[1,4],[1,5]].
| Step | Edge | Roots before | Decision |
|---|---|---|---|
| 1 | [1,2] | 1 and 2 | Different roots, union |
| 2 | [2,3] | 1 and 3 | Different roots, union |
| 3 | [3,4] | 1 and 4 | Different roots, union |
| 4 | [1,4] | 1 and 1 | Same root, return [1,4] |
| 5 | [1,5] | not processed | The answer has already been found |
By step 4, vertices 1 and 4 are connected through 1 - 2 - 3 - 4. Adding [1,4] would create a cycle, so it is the redundant connection.
Interview Tips
Say why Union-Find is enough: we do not need to output the whole cycle, only the edge that first connects two vertices already in the same component. If the interviewer asks for an alternative, describe DFS-per-edge: before adding [u, v], search whether u already reaches v in the graph built so far. That works but costs more repeated traversal and is not the implementation to lead with. Also call out the 1-indexed labels before allocating arrays.
Likely follow-ups
- Return every edge on the cycle, not just the redundant edge.
- What changes if the graph is directed? Compare with Redundant Connection II.
- Support a stream of edge additions and report whether each one creates a cycle.
- After removing the redundant edge, verify that the remaining graph is a valid tree.
Similar Problems
Key Takeaways
- A tree plus one undirected edge creates exactly one cycle.
- The redundant edge is the edge whose endpoints already share a Union-Find root.
- For 1-indexed node labels, allocate parent arrays with one extra slot.
- Union-Find is the optimal fit when edges arrive incrementally and only connectivity matters.