63. Redundant Connection
A tree with nodes 1..n had one extra edge added. Return the edge that can be removed so the graph becomes a tree again. If several qualify, return the one that appears last in edges.
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]Hint 1
Add edges one by one. The first edge whose endpoints are already connected closes a cycle.
Approach 1: DFS before each edge
Check connectivity with a DFS before adding each edge.
Approach 2: Union-Find ✅
The first failed union is the answer.
Reference solution for Union-Find (time O(n · α), space O(n)). Each solution passes every test in all four languages.
class Solution:
def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:
parent = list(range(len(edges) + 1))
def find(x):
while parent[x] != x:
parent[x] = parent[parent[x]]
x = parent[x]
return x
for a, b in edges:
ra, rb = find(a), find(b)
if ra == rb:
return [a, b] # a and b were already connected: this edge makes a cycle
parent[ra] = rb
return []class Solution {
private int[] parent;
private int find(int x) {
while (parent[x] != x) { parent[x] = parent[parent[x]]; x = parent[x]; }
return x;
}
public int[] findRedundantConnection(int[][] edges) {
parent = new int[edges.length + 1];
for (int i = 0; i < parent.length; i++) parent[i] = i;
for (int[] e : edges) {
int a = find(e[0]), b = find(e[1]);
if (a == b) return e; // already connected: cycle
parent[a] = b;
}
return new int[0];
}
}class Solution {
vector<int> parent;
int find(int x) {
while (parent[x] != x) { parent[x] = parent[parent[x]]; x = parent[x]; }
return x;
}
public:
vector<int> findRedundantConnection(vector<vector<int>>& edges) {
parent.resize(edges.size() + 1);
iota(parent.begin(), parent.end(), 0);
for (auto& e : edges) {
int a = find(e[0]), b = find(e[1]);
if (a == b) return e; // already connected: cycle
parent[a] = b;
}
return {};
}
};function findRedundantConnection(edges) {
const parent = [...Array(edges.length + 1).keys()];
const find = x => { while (parent[x] !== x) { parent[x] = parent[parent[x]]; x = parent[x]; } return x; };
for (const [a, b] of edges) {
const ra = find(a), rb = find(b);
if (ra === rb) return [a, b]; // already connected: cycle
parent[ra] = rb;
}
return [];
}Try solving it yourself first. Interviewers care more about how you explain the approach than about the finished code.
Watch the core idea of this problem step by step. Change the input and press Visualize.
Explained in the lesson Topological Sort, Dijkstra & Union-Find.
Run your code to see results here.