Union Find Fundamentals
Union Find Template
Practice Problems
Learning Resources
Union Find Fundamentals
Imagine we have sets of nodes or elements and are asked to check if they belong to a specific set. To solve this kind of question, we can use a union find algorithm on a disjoin union set to visualize our data as a series of trees where certain elements belong to one set only. In this algorithm, we essentially assign one node as the leader/parent of a group and have other nodes point to that parent node's value and save it in a set. That way, if all nodes have one shared parent, we know they belong to that group. Take a look at the illustration below to get a better understanding of this.
Union Find Template
Basic Implementation
class UnionFind:
# initialize the data structure that maps the node to its set ID
def __init__(self):
self.id = {}
# find the Set ID of Node x
def find(self, x):
# get the value associated with key x, if not in map return x
y = self.id.get(x, x)
# check if the current node is a Set ID node
if y != x:
# set the value to Set ID node of node y
y = self.find(y)
return y
# union two different sets setting one Set's parent to the other parent
def union(self, x, y):
self.id[self.find(x)] = self.find(y)
Optimized Implementation
class UnionFind:
def __init__(self):
self.id = {}
def find(self, x):
y = self.id.get(x, x)
if y != x:
# set the value to Set ID node of node y, and change the hash
value of node x to Set ID value of node y
self.id[x] = y = self.find(y)
return y
def union(self, x, y):
self.id[self.find(x)] = self.find(y)The following code accomplishes a union operation in O(1) and a find operation that has best case O(1), average case O(log(n)) since we have a randomized trees which have average depth O(log(n)) and a worst case of O(n) for a maximum depth tree.
Practice Problems
Same Set
Size of Connected Components
Umbristan
Accounts Merge
Number of Connected Components
Number of Islands
Number of Islands II
Graph Valid Tree
Redundant Connection
Redundant Connection II
Friend Circles
Sentence Similarity
Comments