Why is my Union-Find implementation incorrect?


  • 0
    C

    I have been debugging and searching around for a few hours, but still can't find the bug in my implementation.
    Any help is greatly appreciated.

    class DisjointSet(object):
    
        def __init__(self, n): # weighted union-find
            self.size = [1 for i in range(n)]
            self.parent = [i for i in range(n)]
    
        def find(self, p): # path compression
            while p != self.parent[p]:
                self.parent[p] = self.parent[self.parent[p]]
                p = self.parent[p]
            return p
    
        def union(self, p, q):
            r1 = self.find(p)
            r2 = self.find(q)
            if r1 == r2:
                return
            if self.size[p] >= self.size[q]:
                r1, r2 = p, q
            else:
                r1, r2 = q, p
            self.parent[r2] = r1
            self.size[r1] += self.size[r2]
            self.size[r2] = self.size[r1]
    
    
    class Solution:
        def findRedundantConnection(self, edges):
            """
            :type edges: List[List[int]]
            :rtype: List[int]
            """
            DS = DisjointSet(2001)
            redundant = None
            for p, q in edges:
                if DS.find(p) != DS.find(q):
                    DS.union(p, q)
                else:
                    redundant = [p,q]
    
            return redundant
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.