Disjoint Union Set

Stores a collection of disjoint sets. Provides operations for finding, and merging sets. These are typically implemented as a disjoint-set forest.

makeset(x):

• Creates a set of just x find(x):
• Find the representative of a set of a given element.
• The representative is the root of the tree.
• AKA finds the set that x belongs to union(x,y):
• Takes two elements and finds representatives of their sets using Find. Then puts either one of the trees under the root node of the other.

procedure kruskal(G,l)
Input: a connected undirected graph G = (V, E); edge lengths l_e
Output: A minimum spanning tree defned by the edges X
	for all u in V:
		makeset(u)
	X = {0}
	sort the edges E by length  
	for all {u, v} in E in increasing order of length:
		if find(u) != find(v):
			add edge {u, v} to X
			union(u, v)

Disjoint Union Set in 5 minutes

We use a tree data structure for each disjoint set. The root of the tree is the representative or label, this is arbitrary. We then have parent points that lead up to the root of the tree where each vertex has a rank which is the height of the subtree below.

Algorithms

function makeset(x)
pi(x)=x
rank(x)=0

function find(x)
while pi(x) != x:
	x = pi(x)
return x

procedure union(x,y)
r_x = find(x)
r_y = find(y)

if r_x = r_y:
	return
if rank(r_x) > rank(r_y):
	pi(r_y) = r_x // Join the two sets by pointing the root of r_y to r_x
else:
	pi(r_x) = r_y
	// If the trees have the same height, we need to increase the rank of the new root by one
	if rank(r_x) = rank(r_y):
		rank(r_y) = rank(r_y)+1

We can also apply path compression during each find where when parent pointers are followed to the root, we change each pointer so it goes directly to the root:

function find(x)
if pi(x) != x:
	pi(x) = find(pi(x))
return pi(x)

Complexity

The height of the tree is on the order of O(logn) or more specifically O(ElogV). Which is the time complexity of both functions since they both involve traversing up the tree. The space complexity is O(n).