Redundant Connection

Problem

A network was built by adding undirected links one at a time. It started as a tree, so exactly one link too many was added and the network now contains a single cycle. Given the links in the order they were added, return the one that closed the cycle. If more than one would qualify, return the one added last.

Examples

Input:  edges = [[1, 2], [1, 3], [2, 3]]
Output: [2, 3]
Why:    2 and 3 were already connected through 1 when this link arrived

Input:  edges = [[1, 2], [2, 3], [3, 4], [1, 4], [1, 5]]
Output: [1, 4]
Why:    the path 1-2-3-4 already existed, so this link closed the loop

Input:  edges = [[1, 2], [1, 2]]
Output: [1, 2]
Why:    edge case, the same link twice is still a cycle

Hints

0 / 3

1. Hint 1reveal
2. Hint 2locked
3. Hint 3locked

def redundant(edges):
    parent = {}
    def find(x):
        parent.setdefault(x, x)
        while parent[x] != x:
            parent[x] = parent[parent[x]]    # path halving
            x = parent[x]
        return x
    for u, v in edges:
        a, b = find(u), find(v)
        if a == b:                           # already reachable: this closes it
            return [u, v]
        parent[a] = b
    return []

print(redundant([[1, 2], [1, 3], [2, 3]]))                  # -> [2, 3]
print(redundant([[1, 2], [2, 3], [3, 4], [1, 4], [1, 5]]))  # -> [1, 4]
print(redundant([[1, 2], [1, 2]]))                          # -> [1, 2]