[Algorithm] Topic 8: Union Find

Authored by Tony Feng

Created on April 7th, 2022

Last Modified on April 9th, 2022

Understanding Union Find

Intro

A disjoint-set data structure keeps track of a set of elements partitioned into a number of disjoint (non-overlapping) subsets.
A union-find algorithm performs union and find operation on those subsets.
Union-Find Algorithm can be used to check whether an undirected graph contains cycle or not.

Union & Find

Find
- It determines in which subset a particular element is in and returns the representative of that particular set.
Union
- It merges two different subsets into a single subset, and the representative of one set becomes representative of another.

Template

Common Union Find

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18


class UnionFind:
    def __init__(self, n):
        # Initialization. 
        # The parent of each node is itself.
        self.root = list(range(0,n))

    def find(self, x):
        if x == self.root[x]:
            return self.root[x]
        else:
            return self.find(self.root[x])

    def union(self, x, y):
        rootX = self.root[x]
        rootY = self.root[y]

        if rootX != rootY:
            self.root[rootX] = rootY

Union Find Improvement

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26


class UnionFind:
    def __init__(self, n):
        # Initialization. 
        # The parent of each node is itself.
        self.root = list(range(0,n))
        self.rank = [0] * n

    def find(self, x):
        if x != self.root[x]:
            # Use recursion to assign the root value
            self.root[x] = self.find(self.root[x])
        return self.root[x]

    # Avoid the tree to be too high
    def union(self, x, y):
        rootX = self.root[x]
        rootY = self.root[y]

        if rootX != rootY:
            if self.rank[rootX] > self.rank[rootY]:
                self.root[rootY] = rootX
            elif self.rank[rootX] < self.rank[rootY]:
                self.root[rootX] = rootY
            else:
                self.root[rootY] = rootX
                self.rank[rootX] += 1

Examples

Leetcode 200 Number of Islands

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48


# Time Complexity: O(MN)
# Space Complexity: O(MN)
class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        if grid is None or len(grid) == 0:
            return 0
        row = len(grid)
        col = len(grid[0])
        waters = 0
        uf = UnionFind(grid)
        for i in range(0, row):
            for j in range(0, col):
                if grid[i][j] == '0':
                    waters += 1
                else:
                    directions = [(0,1), (0,-1), (-1,0), (1,0)]
                    for x, y in directions:
                        x = x + i
                        y = y + j
                        if x>=0 and y>=0 and x<row and y<col and grid[x][y] == '1':
                            uf.union(x*col+y, i*col+j)
        return uf.getCount() - waters

class UnionFind:
    def __init__(self, grid):
        row = len(grid)
        col = len(grid[0])
        self.root = [-1]*(row*col)
        self.count = row*col
        for i in range(0, row*col):
            self.root[i] = i
    
    def find(self, x):
        if x == self.root[x]:
            return self.root[x]
        else:
            self.root[x] = self.find(self.root[x])
            return self.root[x]
    
    def union(self, x, y):
        rootX = self.find(x)
        rootY = self.find(y)
        if rootX != rootY:
            self.root[rootX] = rootY
            self.count -= 1
    
    def getCount(self):
        return self.count   

Understanding Union Find

Intro

Union & Find

Template

Common Union Find

Union Find Improvement

Examples

Leetcode 200 Number of Islands

Reference