Disjoint-set and Union-find Algorithm

A disjoint-set data structure is a data structure that keeps track of a set of elements partitioned into a number of disjoint(non-overlapping) subsets.

For example: you have three sets which are S1, S2, S3. S1 has A, B, C three elements. S2 has D and E two elements. S3 has X, Y, Z three elements.

S1 & S2 = None, S2 & S3 = None, S1 & S3 = None.

So these are disjoint set as they have no elements in common, or we can say that their intersection(&) with each other is an empty set.

A union-find algorithm is an algorithm that performs two useful operations on such a data structure:

Find: Determine which subset a particular element is in. This can be used for determining if two elements are in the same subset.

Union: Join two subsets into a single subset.

If we use example above, Union(S1, S2) will return a merged set {A, B, C, D, E} named S1, at the same time S2 will be removed.

After that, Find(B) returns S1, Find(D) returns S1, Find(Z) returns S3.

Cycle Detection

For each edge, make subsets using both the vertices of the edge. If both the vertices are in the same subset, a cycle is found.

pseudo code:

1
2
3
4
5
6
7
8
9
10
for each unvisited edge(u, v) in edge set E
{
If (Find(u) == Find(v))
{
// cycle detected
}
else
Union(x, y) // x = Find(u), y = Find(v)
// x is u's presentation, y is v's presentation
}

Init:

0 1 2 3 4
-1 -1 -1 -1 -1

Start:

1
2
Find(0) = 0, Find(1) = 1
=> Union(0,1)
0 1 2 3 4
1 -1 -1 -1 -1
1
2
Find(0) = 1, Find(2) = 2
=> Union(1,2)
0 1 2 3 4
1 2 -1 -1 -1
1
2
Find(2) = 2, Find(3) = 3
=> Union(2,3)
0 1 2 3 4
1 2 3 -1 -1
1
2
Find(3) = 3, Find(4) = 4
=> Union(3,4)
0 1 2 3 4
1 2 3 4 -1
1
2
3
Find(2) = 4, Find(4) = 4
cycle detected
END

Implementation

1
2
3
4
5
6
7
8
9
10
11
12
class DUS:
def __init__(self, length):
self.present = [-1] * length

def find(self, x):
if self.present[x] = -1:
return x
else:
return self.find(self.present[x])

def union(self, x, y):
self.present[find(x)] = find(y)
0%