Redundant Connection

Scan candidate removals from the end of the list backward (so the first one found is the one that “occurs last in the input”). For each candidate, remove it and check whether the remaining n - 1 edges form a connected, acyclic graph over all n nodes.

from collections import deque

class Solution:
    def findRedundantConnection(self, edges: list[list[int]]) -> list[int]:
        n = len(edges)

        def forms_valid_tree(sub_edges):
            graph = {}
            nodes = set()
            for a, b in sub_edges:
                graph.setdefault(a, []).append(b)
                graph.setdefault(b, []).append(a)
                nodes.add(a)
                nodes.add(b)
            if not nodes:
                return True
            start = next(iter(nodes))
            visited = {start}
            queue = deque([start])
            while queue:
                u = queue.popleft()
                for v in graph.get(u, []):
                    if v not in visited:
                        visited.add(v)
                        queue.append(v)
            # connected AND exactly (nodes - 1) edges -> acyclic too
            return len(visited) == len(nodes) and len(sub_edges) == len(nodes) - 1

        for i in range(n - 1, -1, -1):
            candidate = edges[:i] + edges[i + 1:]
            if forms_valid_tree(candidate):
                return edges[i]
        return []

On the example, checking from the end: removing [2,3] (index 2) leaves [[1,2],[1,3]], which connects all 3 nodes with exactly 2 edges — a valid tree. Since this is the first candidate checked (scanning backward), it’s returned immediately: [2,3].

Why it’s correct: exactly one edge in the input is redundant, but if the cycle it closes has length k, any one of those k edges could be removed to break the cycle and produce a valid tree — the constraint “return the one occurring last” is what picks a unique answer, and scanning candidates from the end guarantees the first valid removal found is that one. Complexity: each of the O(n) candidate removals requires an O(n) connectivity check → O(n²) time, O(n) space for one candidate’s graph and visited set at a time.

Process edges in the given order, union-ing each pair of endpoints. The first edge that tries to union two nodes already in the same component is provably the redundant one — every edge before it was needed to build the (still cycle-free) structure, and this is the one extra edge that creates the cycle. Since we scan forward and stop at the first such edge, and only one edge in the whole input can ever trigger this condition, it is automatically the one “occurring last” among any edges that could be removed.

class Solution:
    def findRedundantConnection(self, edges: list[list[int]]) -> list[int]:
        n = len(edges)
        parent = list(range(n + 1))  # nodes are 1-indexed

        def find(x):
            while parent[x] != x:
                parent[x] = parent[parent[x]]  # path compression
                x = parent[x]
            return x

        for a, b in edges:
            root_a, root_b = find(a), find(b)
            if root_a == root_b:
                return [a, b]  # this edge closes a cycle
            parent[root_a] = root_b

        return []

Tracing on the example (parent starts as [0,1,2,3], index 0 unused):

Returns [2, 3], matching the expected output.

The parent-array table focuses on the union-find state. The trace below replays the algorithm on the statement’s longer second example, where find(1) must climb 1 → 2 → 3 → 4 — watch the two find paths land on one shared root, which is the exact moment the edge closes a cycle.

On that example the answer is [1, 4], matching the expected output; the remaining input edge [1, 5] is never scanned because the loop returns the moment a cycle closes.

Why it’s correct: the input graph is a tree plus exactly one extra edge, so scanning edges in order and union-ing them mirrors building that tree back up one edge at a time; the only edge that ever fails to merge two distinct components (because they’re already merged) must be the extra one, since a real tree edge always joins two previously-separate parts. Complexity: n union-find operations, each nearly O(1) amortized with path compression → O(n · α(n)) time, O(n) space for the parent array — a large improvement over re-checking the whole graph for every candidate removal.