This visualization was AI-generated and may contain inaccuracies. Please verify against the original LeetCode problem (#684) before relying on it.

Redundant Connection

An interactive visualization of the Union-Find approach to detecting the redundant edge in an undirected graph. Watch how each edge is processed and how cycle detection identifies the extra connection.

Union-Find LeetCode 684 ↗ Medium

The Problem

You are given a graph that started as a tree with n nodes labeled from 1 to n, with one additional edge added. The added edge connects two vertices that are already in the tree, creating a cycle.

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

Interactive Visualization

Edges (comma-separated pairs)

Preset

Speed:

Edges

Graph

Union-Find State

Code

fun findRedundantConnection(edges: Array<IntArray>): IntArray {    val parent = IntArray(edges.size + 1) { it }    val rank = IntArray(edges.size + 1)    fun find(x: Int): Int {        var x = x; while (parent[x] != x) {            parent[x] = parent[parent[x]]            x = parent[x] }        return x }    fun union(x: Int, y: Int): Boolean {        var px = find(x); var py = find(y)        if (px == py) {            return false }  // cycle!        if (rank[px] < rank[py]) {            val tmp = px; px = py; py = tmp }        parent[py] = px        if (rank[px] == rank[py]) {            rank[px]++ }        return true }    for (edge in edges) {        if (!union(edge[0], edge[1])) {            return edge } } }

def findRedundantConnection(edges):    parent = list(range(len(edges) + 1))    rank = [0] * (len(edges) + 1)    def find(x):        while parent[x] != x:            parent[x] = parent[parent[x]]            x = parent[x]        return x    def union(x, y):        px, py = find(x), find(y)        if px == py:            return False  # cycle!        if rank[px] < rank[py]:            px, py = py, px        parent[py] = px        if rank[px] == rank[py]:            rank[px] += 1        return True    for u, v in edges:        if not union(u, v):            return [u, v]  # redundant edge

Current Step

Press Step or Play to begin.

How It Works

Key Insight

A tree with n nodes has exactly n - 1 edges. When we add one more edge, it must connect two nodes that are already connected, creating a cycle. Union-Find detects this instantly: if find(u) == find(v) before we union them, then u and v are already in the same connected component, and the edge [u, v] is redundant.

The Algorithm

Initialize a Union-Find structure where each node is its own parent (parent[i] = i) and all ranks are 0.
For each edge [u, v], try to union the two nodes:
— Call find(u) and find(v) to get their root representatives.
— If they have the same root: this edge creates a cycle. Return [u, v].
— Otherwise: merge the two sets using union by rank (attach the shorter tree under the taller one).
Path compression in find() flattens the tree for near-constant lookup time.

Complexity

Time O(n * α(n)) ≈ O(n)

Space O(n)

We process each of the n edges once. Each find and union operation takes amortized O(α(n)) time, where α is the inverse Ackermann function — effectively constant for all practical input sizes. The parent and rank arrays use O(n) space.