Problem Statement
Redundant Connection
Picture a bunch of dots, called nodes, with lines drawn between some of them. A line is called an edge. A tree is a special kind of picture where everything is connected in one piece and there are no loops. A loop, also called a cycle, is when you can start at a node, follow edges, and come back to where you started without backtracking. We start with a clean tree that has n nodes numbered 1 to n, then someone adds one extra edge. That extra edge creates exactly one loop. You are given the edges in a list where edges[i] = [ai, bi] is a line between node ai and node bi. Your job is to find one edge you can remove so the picture goes back to being a tree with no loops. If more than one edge would work, return the one that shows up last in the list. The trick: go through the edges in order, and the first edge that joins two nodes that were already connected is the one that closes the loop.
Signals to notice
Brute force first
For each edge, remove it and check if the remaining graph is still a tree. Rebuilds the graph for every edge. It is a fair place to begin because it matches the surface of the question, yet it does not capture the deeper structure that makes the problem simpler.
The key insight
Union-Find: process edges one by one. If union(u,v) finds they're already connected, this edge creates a cycle — it's the redundant edge. Instead of recomputing the world every time, you preserve just enough context to let the next decision become obvious.
Trace it on edges = [[1,2],[2,3],[3,4],[1,4],[1,5]]
init: parent=[0,1,2,3,4,5], rank=[0,0,0,0,0,0] edge [1,2]: find(1)=1, find(2)=2 -> differ; union: parent[2]=1, rank[1]=1 edge [2,3]: find(2)=1, find(3)=3 -> differ; rank[1]>rank[3] so parent[3]=1 edge [3,4]: find(3)=1, find(4)=4 -> differ; rank[1]>rank[4] so parent[4]=1 edge [1,4]: find(1)=1, find(4)=1 -> SAME root -> cycle detected return [1,4] (edge [1,5] never processed)
What must stay true
In a tree with n nodes, there are exactly n-1 edges. The graph has n edges, so exactly one is redundant. That edge connects two nodes already in the same component — detected by Union-Find. As long as that statement keeps holding, you can trust the steps built on top of it.
Shape of the loop
parent[i] = i for all nodes; rank[i] = 0
find(x): follow parent to root, compress path
for (u, v) in edges:
if find(u) == find(v): return [u, v] # already connected -> redundant
union by rank: attach smaller-rank root under largerPseudocode only — the full worked solution lives in the Solution tab.
Easy way to go wrong
Returning the first cycle edge found — the problem asks for the LAST such edge in the input order. Process all edges; the last one that causes a union to fail is the answer. Most mistakes here are not about syntax; they come from losing track of what your state, pointer, or structure is supposed to mean.