DSA: Disjoint Union Set

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

---

Learning Resources

1. Union find - Algorithmist

2. Leetcode-Union-Find Data Sturcture | by Yunrui Li | Medium