Leetcode 684 Solution

This article provides solution to leetcode question 684 (redundant-connection)
Categories:
Tags:
Access this page by simply typing in "lcs 684" in your browser address bar if you have bunnylol configured.

https://leetcode.com/problems/redundant-connection

Solution

class FindUnionSet:
    def __init__(self, N):
        self.p = list(range(N))

    def find(self, i):
        if self.p[i] != i:
            self.p[i] = self.find(self.p[i])
        return self.p[i]

    def union(self, i, j):
        pi = self.find(i)
        pj = self.find(j)
        self.p[pi] = pj


class Solution:
    def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:
        N = max([max(src, dst) for src, dst in edges])
        fuset = FindUnionSet(N + 1)
        for src, dst in edges:
            if fuset.find(src) == fuset.find(dst):
                return [src, dst]
            fuset.union(src, dst)