union_find.md

Union Find

• Union Find (or disjoint-set) is a very elegant data structure
• Essentially it utilizes a list representation for the joint data points
  • the index of the data point indicates its linkage status
• For detailed explanation, please see this Lecture Notes

Template

class UnionFind:
    def __init__(self, n):
        self.count = n
        self.parent = list(range(n))  # root list
        self.size = [1] * n  # weight
        
    def find(self, i):
        while self.parent[i] != i:
            self.parent[i] = self.parent[self.parent[i]]  # Path compression
            i = self.parent[i]
        return i
    
    def union(self, p, q):
        i, j = self.find(p), self.find(q)
        
        if i == j:
            return 

        # merge smaller tree into larger tree to obtain a flat structure
        if self.size[i] < self.size[j]:
            self.parent[i] = j
            self.size[j] += self.size[i]
        else:
            self.parent[j] = i
            self.size[i] += self.size[j]
        
        self.count -= 1

Reference:

• Union Find with Explanations (Java / Python)
• [Python] Solved by Union Find Template
• Python, Weighted Union+Find with Path Compression
• [Python3] Classic Union Find Solution

Practice:

• 684. Redundant Connection
• 547. Number of Provinces
• 765. Couples Holding Hands
• 305. Number of Islands II