There is exactly one cycle. Its final input edge is the first whose endpoints have already been joined along the rest of that cycle. It is therefore the failed union.

Before each edge, DSU represents connectivity using previous edges. Different roots mean the new edge joins two components. Equal roots mean an existing path already connects them, so adding the edge forms an undirected cycle. The implementation keeps the latest failure; under the tree-plus-one-edge contract there is exactly one.

What the function promises: Edges use positive integer labels and describe an undirected tree plus one extra edge, with no self-loops or parallel edges. Return the last removable edge in input order. Empty input returns None as a helper extension.

class DisjointSet:
    def __init__(self, n):
        self.parent = list(range(n))
        self.size = [1] * n

    def find(self, x):
        while x != self.parent[x]:
            self.parent[x] = self.parent[self.parent[x]]
            x = self.parent[x]
        return x

    def union(self, a, b):
        a, b = self.find(a), self.find(b)
        if a == b:
            return False
        if self.size[a] < self.size[b]:
            a, b = b, a
        self.parent[b] = a
        self.size[a] += self.size[b]
        return True

def redundant_edge(edges):
    n = max((max(u, v) for u, v in edges), default=0)
    groups = DisjointSet(n + 1)
    answer = None
    for u, v in edges:
        if not groups.union(u, v):
            answer = (u, v)
    return answer

assert redundant_edge([(1, 2), (2, 3), (1, 3)]) == (1, 3)
assert redundant_edge([(1, 2), (1, 3), (2, 3)]) == (2, 3)
assert redundant_edge([]) is None

Work and storage: O(V + E α(V)) time and O(V) space for labels 1..V. Labels with huge gaps should be compressed instead of allocating up to their numeric maximum.

When to recognize it: An edge whose endpoints already share a group closes a cycle.

Check before applying it: This test is for undirected connectivity. A→B, A→C, B→C has no directed cycle even though ignoring arrows forms a triangle.

No. A→B, A→C, B→C is acyclic but its undirected version closes a triangle. Use directed DFS with active/finished states or topological cycle detection.