Redundant Connection

You are given edges of an undirected graph that started as a tree with one extra edge added. Return the edge that creates the cycle.

Why this is worth learning

Union-find summarizes connectivity of the edges already accepted. Adding an edge inside one connected component closes a cycle; adding one between components joins them safely.

Before coding: one-minute experiment

For edges [1,2], [2,3], [1,3], which edge is rejected? Why would simply comparing the two immediate parent array entries be unsafe?

Function signature

func FindRedundantConnection(edges [][]int) []int

Inputs / outputs

• edges: list of undirected edges, nodes are labeled from 1..n.
• Return: the edge that can be removed to make the graph a tree.

Example

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

Constraints

• 3 <= n <= 100_000
• Exactly n undirected edges describe a tree on labels 1..n plus one additional edge. Return the last edge of its unique cycle in input order, preserving that pair's orientation.

Core idea (near-solution)

A direct approach processes edges in order and searches the accepted graph before adding each edge: if its endpoints are already reachable from one another, the new edge closes a cycle. Repeated searches do more work than needed when edges are only added. Keep the partition into connected components instead; find retrieves a representative and union merges two different components. Under the tree-plus-one-edge promise, the first rejected edge is the last input edge on that single cycle. This summary represents undirected connectivity, not directed reachability.

Invariant: find(x) returns the representative of x's connected component.

Algorithm (step-by-step)

1. Initialize DSU for nodes 1..n.
2. For each edge (u, v):
   • If find(u) == find(v), return [u, v].
   • Otherwise union(u, v).
3. (By problem guarantee, you will return inside the loop.)

Correctness sketch

Initially every vertex is its own component. By induction, union operations make two vertices share a representative exactly when accepted edges connect them. If a new edge has different representatives, joining it cannot form a cycle, and union preserves the invariant. If its endpoints already share a representative, the accepted graph contains a path between them, so the new edge closes a cycle. Under the tree-plus-one-edge contract there is exactly one cycle; the detected edge is the last edge of that cycle in input order, and removing it leaves a connected acyclic graph. This argument is not a detector for arbitrary directed cycles.

Trace (hand walkthrough)

Example input:
edges = [[1,2],[1,3],[2,3]]
Output: [2,3]

Walk:
- union 1-2 (ok), union 1-3 (ok)
- union 2-3 finds same root -> redundant edge [2,3]

Pitfalls to avoid

• Forgetting path compression (can be slow on large inputs).
• Using 0-based DSU when nodes are 1-based.

Debugging lens

Test a long chain closed by its final edge and a cycle whose last input edge is not the originally added edge in your drawing. Preserve the original orientation of the returned pair.

Complexity

Time O(n alpha(n)) amortized with union by rank and path compression, including the initial label scan; alpha is the inverse Ackermann function. Auxiliary space O(n) under labels 1..n.

Implementation notes (Go)

• Use parent and rank/size slices for DSU.

Contract precision

For this tree-plus-one-edge input, the reference returns the last cycle edge in input order. Several edges could individually be removed to restore a tree; this tie rule preserves the existing observable result.

Reconstruction checkpoint

Process [1,2], [2,3], [3,4], [1,4]. What does the last edge add to reachability, and why is it the requested edge even though removing any edge on the cycle would restore a tree?

Return to Graph General · Module quiz