#684

Redundant Connection

medium· Graphsruns: 0

In a graph that started as a tree of n nodes labeled 1 to n, one additional edge was added. You are given the resulting array of edges. Return an edge that can be removed so that the result is a tree of n nodes. If there are multiple answers, return the one that occurs last in the input.

wpm 0acc 100%time 0:000 / 840

class Solution:
    def findRedundantConnection(
        self, edges: list[list[int]]
    ) -> list[int]:
        parent = list(range(len(edges) + 1))
        rank = [1] * (len(edges) + 1)

        def find(n: int) -> int:
            while parent[n] != n:
                parent[n] = parent[parent[n]]
                n = parent[n]
            return n

        def union(a: int, b: int) -> bool:
            ra, rb = find(a), find(b)
            if ra == rb:
                return False
            if rank[ra] < rank[rb]:
                parent[ra] = rb
            elif rank[ra] > rank[rb]:
                parent[rb] = ra
            else:
                parent[rb] = ra
                rank[ra] += 1
            return True

        for a, b in edges:
            if not union(a, b):
                return [a, b]
        return []

click the box to focus · tab inserts 4 spaces · backspace to correct · esc to pause

desktop only

codedrill is a typing game and needs a real keyboard. open this on a laptop or desktop to practice.

you can still browse problems and sections from your phone.