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.

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

Core idea (near-solution)

Use Union-Find (Disjoint Set Union). If an edge connects two nodes already in the same set, it is redundant.

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

• Invariant: find(x) returns the representative of x's connected component.
• Union-Find tracks connectivity of components as edges are added.
• An edge connecting two nodes in the same component forms a cycle.
• The first such edge is therefore redundant.

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.

Complexity

• Time: almost O(n) with path compression.
• Extra space: O(n).

Implementation notes (Go)

• Use parent and rank/size slices for DSU.