Skip to content

Instantly share code, notes, and snippets.

@anish000kumar
Last active July 18, 2020 22:09
Show Gist options
  • Save anish000kumar/4d4d903e5e6941ab85028fcef68954ae to your computer and use it in GitHub Desktop.
Save anish000kumar/4d4d903e5e6941ab85028fcef68954ae to your computer and use it in GitHub Desktop.
Quick Disjoint Set in python (Union Find with path compression)
class Node:
def __init__(self, value):
self.value = value
self.rank = 1
self.parent = self
class DisjointSet:
def __init__(self):
self.mapping = {}
def find(self, u):
if u not in self.mapping:
self.mapping[u] = Node(u)
node = self.mapping[u]
if node.parent is not node:
node.parent = self.find(node.parent.value) #path compression
return node.parent
def union(self, u, v):
p1, p2 = self.find(u), self.find(v)
if p1 is p2: return False
if p1.rank < p2.rank:
p1.parent = p2
elif p2.rank < p1.rank:
p2.parent = p1
else:
p2.parent = p1
p1.rank += 1
return True
# example usage to find cycle in undirected graph
# https://leetcode.com/problems/redundant-connection/
def findCycle(self, edges: List[List[int]]) -> List[int]:
dset = DisjointSet()
for u, v in edges:
if not dset.union(u, v):
return [u, v]
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment