Redundant Connection

def findRedundantConnection(edges):
    parent = list(range(len(edges) + 1))
    rank = [0] * (len(edges) + 1)
    def find(x):
        if parent[x] != x:
            parent[x] = find(parent[x])  # compress
        return parent[x]
    for a, b in edges:
        ra, rb = find(a), find(b)
        if ra == rb:
            return [a, b]        # same root
        if rank[ra] < rank[rb]:
            ra, rb = rb, ra
        parent[rb] = ra          # union by rank
        if rank[ra] == rank[rb]:
            rank[ra] += 1

Redundant Connection. A tree of n nodes gets one extra edge, which makes a loop. Return an edge you can remove to get a tree back. If several work, return the last one in the input.

Take edges one two, one three, and two three. They form a triangle. Removing any of them leaves a tree, so return the last one: two three.

The simple way: before adding each edge, search the graph built so far, to see if its ends are already connected. If they are, this edge closes the loop. Each search can visit every node, so that's order n squared.

Union-find does better. Each node points to a parent, and following parents leads to its group's root. Find returns that root. Union joins two groups by pointing one root at the other. If an edge's ends already share a root, it's redundant.

In code, every node starts as its own parent. For each edge, find both roots. If they match, return the edge. Otherwise, hang the shorter tree under the taller one: union by rank. And find points each node it passes straight at the root: path compression.

Try edges one two, two three, three four, one four, and one five. One two: different roots, so join them under one. Two three: two's root is one, so three joins. Three four: four joins too. One four: both roots are one. Return one four.

With both tricks, each find takes nearly constant time, so the whole run is about order n. Space is order n, for the parent and rank arrays.

Same root, already connected. That's Redundant Connection.