# Why is my Union-Find implementation incorrect?

• 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
``````

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