Redundant Connection

Problem

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, with one additional edge added. Return an edge that can be removed so that the resulting graph is a tree of n nodes.

Examples

The brute-force approach

Try removing each edge (starting from the last). Check if the remaining graph is still connected. Return the first removal that keeps the graph a valid tree.

for i in range(len(edges)-1, -1, -1):
    remaining = edges[:i] + edges[i+1:]
    if is_valid_tree(n, remaining):
        return edges[i]

O(E × (V+E)) — for each edge, check connectivity. Very slow.

Spotting the pattern

This is a Union-Find problem. The key question to ask yourself:

If you process edges in order and union their endpoints, when would you first detect a cycle?

Answering that is where it clicks, and it's exactly what the guided walkthrough below builds with you: the pattern reasoning, a progressive hint ladder that never spoils the answer, a row-by-row dry run, the optimized solution, and an in-browser editor to run your code against real test cases.