Redundant Connection

You are given a graph that started as a tree with n nodes labeled from 1 to n.

One additional edge was added to the tree, creating exactly one cycle.

Return the edge that can be removed so that the resulting graph becomes a tree again.

If multiple answers are possible, return the edge that appears last in the input.

Example

edges =

1 - 2

1 - 3

2 - 3

The graph is:

    1

   / \

  2---3

The edge:

2 - 3

creates the cycle.

Therefore, the answer is:

[2, 3]

Main Idea

This problem can be efficiently solved using Union Find (Disjoint Set Union).

Initially, every node belongs to its own set.

For every edge:

u - v

check whether u and v already belong to the same set.

If they belong to different sets

Join them:

Union(u, v)

If they already belong to the same set

Adding this edge creates a cycle.

Therefore, this is the redundant edge.

For example:

1 - 2

1 - 3

2 - 3

After processing:

1 - 2

1 and 2 are connected.

Then:

1 - 3

3 joins the same component.

Finally:

2 - 3

Both are already in the same component.

Therefore:

[2, 3]

is the redundant connection.