203. Redundant Connection

Why this mechanism works

An edge creates an undirected cycle exactly when a path already joins its endpoints. DSU tests this condition without reconstructing the path. Scan in the supplied order and return the first failed union, rather than sorting edges or choosing the last failure.

State and boundaries

DSU represents connectivity from the edge prefix before the current edge. A false union result is the redundancy witness.

Protocol

1. Create singleton components.
2. Read edges in input order.
3. Attempt each union.
4. Return the current pair on the first false result.
5. Return None if no union fails.

Visualization

0-1 accepted; 1-2 accepted
0-2 finds both endpoints in the same component
return (0,2) before considering later edges

Python implementation

from kata_201 import DSU

def first_redundant_edge(n, edges):
    dsu = DSU(n)
    for a, b in edges:
        if not dsu.union(a, b):
            return (a, b)
    return None

Worked execution

Recorded state changes after statements; L numbers refer to the solution file. Long traces are explicitly condensed.

L4 first_redundant_edge: dsu = DSU(n)
n=3; edges=[(0, 1), (1, 2), (0, 2)]; dsu=DSU{'parent':[..., ..., ...], 'size':[..., ..., ...], 'count':3}

L5 first_redundant_edge: for a, b in edges:
n=3; edges=[(0, 1), (1, 2), (0, 2)]; dsu=DSU{'parent':[..., ..., ...], 'size':[..., ..., ...], 'count':3}; a=0; b=1

L6 first_redundant_edge: if not dsu.union(a, b):
n=3; edges=[(0, 1), (1, 2), (0, 2)]; dsu=DSU{'parent':[..., ..., ...], 'size':[..., ..., ...], 'count':2}; a=0; b=1

L5 first_redundant_edge: for a, b in edges:
n=3; edges=[(0, 1), (1, 2), (0, 2)]; dsu=DSU{'parent':[..., ..., ...], 'size':[..., ..., ...], 'count':2}; a=1; b=2

L6 first_redundant_edge: if not dsu.union(a, b):
n=3; edges=[(0, 1), (1, 2), (0, 2)]; dsu=DSU{'parent':[..., ..., ...], 'size':[..., ..., ...], 'count':1}; a=1; b=2

L5 first_redundant_edge: for a, b in edges:
n=3; edges=[(0, 1), (1, 2), (0, 2)]; dsu=DSU{'parent':[..., ..., ...], 'size':[..., ..., ...], 'count':1}; a=0; b=2

L4 first_redundant_edge: dsu = DSU(n)
n=2; edges=[(0, 1)]; dsu=DSU{'parent':[..., ...], 'size':[..., ...], 'count':2}

L5 first_redundant_edge: for a, b in edges:
n=2; edges=[(0, 1)]; dsu=DSU{'parent':[..., ...], 'size':[..., ...], 'count':2}; a=0; b=1

L6 first_redundant_edge: if not dsu.union(a, b):
n=2; edges=[(0, 1)]; dsu=DSU{'parent':[..., ...], 'size':[..., ...], 'count':1}; a=0; b=1

Why the solution is correct

If endpoints are already connected, their existing path plus the new edge forms a cycle, so that edge is redundant. Otherwise it merges components and creates no cycle. Because the scan stops at the first such case, the returned edge is the earliest required witness.

Time and space

O(n+m*alpha(n)) amortized worst-case time and O(n) storage, with early exit possible.

Common mistakes

Returning the final failed union violates this first-edge contract. Sorting the input changes which edge is first.

Reasoning card

Transfer exercise

Return the actual cycle by retaining accepted forest edges and finding the existing endpoint path when union fails.