Redundant Connection

Find the extra edge that creates a cycle in an undirected graph.

graphs union-find cycle-detection edges

In this problem, a tree is an undirected graph that is connected and has no cycles. You are given a graph that started as a tree with `n` nodes (labeled from `1` to `n`) and one extra edge was added. The graph is still connected, but now it has exactly one cycle. The extra edge does not have to connect two distinct nodes (it could be a self-loop).

Write a function `find_redundant_connection(edges)` that takes a list of edges, where each edge is a list `[u, v]` representing an undirected connection between nodes `u` and `v`, and returns the edge that appears last in the input and is redundant (i.e., it closes the cycle). If multiple edges could be removed to make the graph a tree, return the one that occurs last in the input.

You can assume that the input satisfies the conditions described above: the graph is connected, has exactly `n` nodes, has exactly `n` edges, and exactly one edge is redundant.

Your solution should be efficient even for larger graphs.

Constraints

- `2 <= len(edges) <= 1000`
- `edges[i]` is a list of two integers `[u, v]` with `1 <= u, v <= len(edges)`.
- The graph is connected and has exactly one cycle.
- The input may contain self-loops (u == v).
- Return the redundant edge as a list `[u, v]` in its original order.

Example

```python
>>> find_redundant_connection([[1,2],[1,3],[2,3]])
[2, 3]
>>> find_redundant_connection([[1,2],[2,3],[3,4],[1,4],[1,5]])
[1, 4]
>>> find_redundant_connection([[1,2],[2,3],[3,1]])
[3, 1]
```

25 points ~25 min

Recent Submissions

No submissions yet — hit Run Tests to try!

Hints

Think about adding edges one by one and detecting when adding an edge connects two nodes that are already in the same connected component.

The union-find (disjoint set) data structure is perfect for this: when you find that the endpoints of an edge are already in the same set, that edge is redundant.

If you add edges in order, the first edge that connects two nodes already connected is the redundant one. But careful: the problem asks for the edge that appears last in the input among all possible redundant edges. In a graph with exactly one cycle, the first such edge you encounter is actually the last in the input.

You can also implement a DFS-based cycle detection: build the graph incrementally and check if adding an edge creates a cycle. The first time it does, that edge is the answer.

Test Results

Press Ctrl+Enter or click Run Tests to execute your code.