The Simple Tutorial to Disjoint Set (Union Find Algorithm)

Disjoint Sets is one of the most powerful and yet simple data structure. The idea of Disjoint Sets can be perfectly applied in finding the minimal spanning tree. The Disjoint Sets consist of two basic operations: finding the group (parent) of any element, unioning two or more sets.

Considering above forests (a set of trees), each tree represents a set. We use an one-dimension array to store the fathers of every node. We can initialize them by -1 or itself, meaning they belong to their own group at the begining. Otherwise, the value represents its father node.

Finding the root-parent of any group can be implemented by two styles: recursive or iterative. The recursive method is short and straightforward.

1
2
3
4
5

def find(x):
    global father
    if x != father[x]:
        father[x] = find(x) // compress the paths
    return father[x]

def find(x):
    global father
    if x != father[x]:
        father[x] = find(x) // compress the paths
    return father[x]

The iterative approach is more efficient and it avoids stack overflow if the path sometimes is degenerated into a linked-list. In this case, the root-finding complexity will be .

1
2
3
4
5
6
7
8
9
10
11

def find(x):
    global father
    px = x
    while px != father[px]:
        px = father[px] // trace to root
    // path compression
    while x != px:
        i = father[x]
        father[x] = px // link to root
        x = i
    return px

def find(x):
    global father
    px = x
    while px != father[px]:
        px = father[px] // trace to root
    // path compression
    while x != px:
        i = father[x]
        father[x] = px // link to root
        x = i
    return px

By checking the root-parents of two element, we can judge if they belong to the same set (same tree).

1
2

def same(x, y):
    return find(x) == find(y)

def same(x, y):
    return find(x) == find(y)

The above shows how to union two sets. We can simply point the father of one element to the other element in other set. e.g. father[x] = y where x and y belong to different sets. The rank array is optional. It represents the depth of an element. We can use the rank to merge two sets i.e. by pointing the less-depth set to a more-depth set.

1
2
3
4
5
6
7
8
9
10
11

def union(x, y):
    global father, rank
    x = find(x)
    y = find(y)
    if x == y: return  // same set
    if rank[x] > rank[y]:
        father[y] = x
    else:
        if rank[x] == rank[y]:
            rank[y] += 1 // update the rank
        father[x] = y

def union(x, y):
    global father, rank
    x = find(x)
    y = find(y)
    if x == y: return  // same set
    if rank[x] > rank[y]:
        father[y] = x
    else:
        if rank[x] == rank[y]:
            rank[y] += 1 // update the rank
        father[x] = y

We can keep a shorter (less depth) tree in this method, which will shorten the time in finding the root, apart from the optimisation using path compression described above.

Disjoint Sets uses space.

Number of Connected Groups

We can count the number of connected groups by checking the final group IDs:

1
2
3
4
5

def size(parents):
  for i, v in enumerate(parents):
     if i == v:
        ans += 1
  return ans

def size(parents):
  for i, v in enumerate(parents):
     if i == v:
        ans += 1
  return ans

Here is another Union Find: The Union Find (Disjoint Set) Implementation in Java

We can also keep a variable counter for the current connected Groups and update it when we merge two components. This will be O(1) time.

Disjoint Set Python Template Class

Here is a template of Python Disjoint Set: https://github.com/DoctorLai/ACM/blob/master/template/DSU.py

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

class UnionFind:
    def __init__(self, n: int):
        self.parent = list(range(n))
        self.size = [1] * n
        self.n = n
        self.setCount = n
    
    def findset(self, x: int) -> int:
        if self.parent[x] == x:
            return x
        self.parent[x] = self.findset(self.parent[x])
        return self.parent[x]
    
    def unite(self, x: int, y: int) -> bool:
        x, y = self.findset(x), self.findset(y)
        if x == y:
            return False
        if self.size[x] < self.size[y]:
            x, y = y, x
        self.parent[y] = x
        self.size[x] += self.size[y]
        self.setCount -= 1
        return True
    
    def connected(self, x: int, y: int) -> bool:
        x, y = self.findset(x), self.findset(y)
        return x == y

class UnionFind:
    def __init__(self, n: int):
        self.parent = list(range(n))
        self.size = [1] * n
        self.n = n
        self.setCount = n
    
    def findset(self, x: int) -> int:
        if self.parent[x] == x:
            return x
        self.parent[x] = self.findset(self.parent[x])
        return self.parent[x]
    
    def unite(self, x: int, y: int) -> bool:
        x, y = self.findset(x), self.findset(y)
        if x == y:
            return False
        if self.size[x] < self.size[y]:
            x, y = y, x
        self.parent[y] = x
        self.size[x] += self.size[y]
        self.setCount -= 1
        return True
    
    def connected(self, x: int, y: int) -> bool:
        x, y = self.findset(x), self.findset(y)
        return x == y

–EOF (The Ultimate Computing & Technology Blog) —