Union Find

Use Cases for Union Find

Use Case	Description	Example
Connected Components	Determine if two nodes are in the same connected component in a graph.	In a social network, check if two users are in the same group.
Network Connectivity	Monitor the connectivity of a network as connections are added or removed.	In a computer network, determine if two devices can communicate after a new connection is made.
Kruskal's Minimum Spanning Tree	Use Union-Find to detect cycles while constructing a minimum spanning tree.	In a graph of cities, find the minimum cost to connect all cities without any cycles.

Code Template

Initializing variables

self.parent = [i for i in range(size)]: Creates a parent array where each element points to itself, indicating that each element is its own set initially.
self.rank = [1] * size: Initializes a rank array, where each element starts with a rank of 1, used to optimize union operations by keeping track of tree depth.

Find function

This method is designed to find the root or representative of the set containing element p.
if self.parent[p] != p: This line checks if the element p is its own parent. If not, it means p is not the root of its set.
self.parent[p] = self.find(self.parent[p]): If p is not the root, this line recursively calls find on p's parent. The result is then assigned back to self.parent[p], effectively flattening the structure (path compression). This means that all nodes in the path from p to its root will now point directly to the root, speeding up future queries.

Union function

rootP = self.find(p) and rootQ = self.find(q): Use find to get the representative roots for p and q.
If both roots are already the same, union returns False because no merge happened.
Otherwise, the root with the higher rank becomes the parent. If ranks are equal, one root becomes the parent and its rank is incremented. Return True to signal that two components were merged.

Check connection

connected(p, q) compares the roots of p and q. If the roots are the same, both nodes are in the same connected component.

class UnionFind:
    def __init__(self, size):
        self.parent = [i for i in range(size)]
        self.rank = [1] * size

Common mistakes

Wrong Path Compression Implementation

# Wrong: no path compression
def find(self, p):
    while self.parent[p] != p:  # Just traverses up
        p = self.parent[p]
    return p
# Wrong: incorrect recursion
def find(self, p):
    if self.parent[p] != p:
        return self.find(self.parent[p])  # Doesn't compress
# Correct:
def find(self, p):
    if self.parent[p] != p:
        self.parent[p] = self.find(self.parent[p])
    return self.parent[p]

Wrong Union by Rank Implementation

# Wrong: not using ranks
def union(self, p, q):
    rootP = self.find(p)
    rootQ = self.find(q)
    self.parent[rootQ] = rootP  # Always merges to rootP
# Wrong: incorrect rank update
def union(self, p, q):
    if self.rank[rootP] == self.rank[rootQ]:
        self.rank[rootP] += 1
        self.rank[rootQ] += 1  # Should only increment one
# Correct:
if self.rank[rootP] == self.rank[rootQ]:
    self.parent[rootQ] = rootP
    self.rank[rootP] += 1

Wrong Connected Check

# Wrong: not using find
def connected(self, p, q):
    return self.parent[p] == self.parent[q]  # Should use find()
# Wrong: redundant finds
def connected(self, p, q):
    rootP = self.find(p)
    rootQ = self.find(q)
    return self.find(rootP) == self.find(rootQ)  # Unnecessary finds
# Correct:
def connected(self, p, q):
    return self.find(p) == self.find(q)

Issues and consideration

Thread Safety: If the class is intended for concurrent use, consider implementing locking mechanisms to prevent race conditions.

200. Number of Islands

class UnionFind:
    def __init__(self, size):
        self.parent = [i for i in range(size)]
        self.rank = [1] * size

    def find(self, p):
        if self.parent[p] != p:
            self.parent[p] = self.find(self.parent[p])
        return self.parent[p]

    def union(self, p, q):
        rootP = self.find(p)
        rootQ = self.find(q)

        if rootP == rootQ:
            return False

        if self.rank[rootP] > self.rank[rootQ]:
            self.parent[rootQ] = rootP
        elif self.rank[rootP] < self.rank[rootQ]:
            self.parent[rootP] = rootQ
        else:
            self.parent[rootQ] = rootP
            self.rank[rootP] += 1
        return True

    def connected(self, p, q):
        return self.find(p) == self.find(q)

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        if not grid:
            return 0
        
        rows = len(grid)
        cols = len(grid[0])
        
        uf = UnionFind(rows * cols)
        count = 0

        for i in range(rows):
            for j in range(cols):
                if grid[i][j] == "1":
                    count += 1
                    for di, dj in [(0, 1), (1, 0)]:
                        ni, nj = i + di, j + dj
                        if (0 <= ni < rows and 
                            0 <= nj < cols and 
                            grid[ni][nj] == "1"):
                            if uf.union(i * cols + j, ni * cols + nj):
                                count -= 1

        return count

547. Number of Provinces

class UnionFind:
    def __init__(self, size):
        self.parent = [i for i in range(size)]
        self.rank = [1] * size

    def find(self, p):
        if self.parent[p] != p:
            self.parent[p] = self.find(self.parent[p])
        return self.parent[p]

    def union(self, p, q):
        rootP = self.find(p)
        rootQ = self.find(q)

        if rootP == rootQ:
            return False

        if self.rank[rootP] > self.rank[rootQ]:
            self.parent[rootQ] = rootP
        elif self.rank[rootP] < self.rank[rootQ]:
            self.parent[rootP] = rootQ
        else:
            self.parent[rootQ] = rootP
            self.rank[rootP] += 1
        return True

    def connected(self, p, q):
        return self.find(p) == self.find(q)

class Solution:
    def findCircleNum(self, isConnected: List[List[int]]) -> int:
        if not isConnected:
            return 0

        n = len(isConnected)
        uf = UnionFind(n)
        provinces = n

        for i in range(n):
            for j in range(i + 1, n):
                if isConnected[i][j] == 1 and uf.union(i, j):
                    provinces -= 1

        return provinces

Union Find

Use Cases for Union Find

Code Template

Initializing variables

Find function

Union function

Check connection

Common mistakes

Issues and consideration

Related Problem

Resources