Skip to content

Union Find Data Structure

The Union Find data structure has mainly 3 operations: - MakeUnionFind(SS) - set up singleton components s,s∈Ss, s\in S - find(ss) - find the component that contains element ss - union(s,s′s,s') - merge two components ss and s′s'

Basic Setup (or Notations)

Let us consider a set SS partitioned into the components {c1,c2,...cj}\{c_1,c_2,...c_j\} with only a single element s∈S,s\in S, i.e., each ss belongs to a single component

Implementation

Naive Implementation

  • Let us assume S={0,1,2,...,n−1}S=\{0,1,2,...,n-1\}

  • Create a dictionary component

  • Now for the function MakeUnionFind(S) - Set component[i] = i for each i∈Si\in S

  • For the function find(i) - return component[i]

  • And for the function union(i, j) - set all the ss from the component ii to jj
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class UnionFind:
    def __init__(self):
        self.component = {}

    def MakeUnionFind(self, S):
        self.component = {i: i for i in S}
        self.n = len(S)

    def find(self, i):
        return self.component[i]

    def union(self, i, j):
        c_old = self.components[i]
        c_new = self.components[j]
        for k in range(self.n):
            if component[k] == c_old:
                component[k] = c_new

A better Implementation

As we saw above, the union function was inefficient.

So to improve that, we could create two more dictionaries members and sizes, where members[c] = list of all members of the component c and sizes[c] = len(members[c])

 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
class UnionFind:
    def __init__(self):
        self.component = {}
        self.members = {}
        self.sizes = {}

    def MakeUnionFind(self, S):
        for i in S: 
            self.component[i] = i
            self.members[i] = [i]
            self.size[i] = 1
        self.n = len(S)

    def find(self, i):
        return self.component[i]

    def union(self, i, j):
        c_old = components[i]
        c_new = components[j]

        if self.size[c_old] > self.size[c_new]:
            return union(self, j, i)

        for k in members[i]:
            self.components[k] = c_new
            self.members[j].append(k)
            self.size[c_new] += 1

        self.members[i] = []
        self.size[c_old] = 0

Time Complexity

Basic Implementation

The time complexity of the funtions are: - MakeUnionFind - O(n)O(n) - find(i) - O(1)O(1) - union(i,j) - O(n)O(n)

A Better Implementation

The time complexity of the funtions are: - MakeUnionFind - O(n)O(n) - find(i) - O(1)O(1) - union(i,j) - O(size(Smaller Set))O(\text{size(Smaller Set)}) - Average Cost of mm union operations - O(mlog⁡m)O(m\log m)