Disjoint Sets: Linked-List Representation | Algorithms II

Flat Forest (Array of Representatives)

The simplest implementation: each element stores a pointer to its set’s representative.

Operation	Implementation	Cost
`MakeSet(x)`	Set `x.rep = x`	$\Theta(1)$
`Find(x)`	Return `x.rep`	$\Theta(1)$
`Union(x, y)`	For all elements, if `rep == y`, change to `x`	$\Theta(n)$

This is the “flat forest”: every element points directly to the representative. Find is instant; Union scans the entire universe of elements.

Weighted-Union Heuristic for Flat Forest

The $\Theta(n)$ cost of Union can be improved. Instead of scanning all $n$ elements, maintain each set as a linked list with head and tail pointers. Each element stores a pointer to the head (representative).

For Union(A, B): walk through the shorter list and update each element’s representative to point to the head of the longer list. This is the weighted-union heuristic.

Analysis

When an element’s representative changes, the set it belongs to at least doubles in size (it was in the smaller list, which gets merged into the larger). Since the maximum set size is $n$ , each element’s representative can change at most $\log_2 n$ times.

Total work over $n-1$ Union operations starting from $n$ singletons:

$\text{Total} \le \sum_{\text{each element}} \log_2 n = n \log_2 n$

Total operations: $n$ MakeSet + $(n-1)$ Union + (some number of) Find. Total time $O(n + n \log n + m) = O(m + n \log n)$ .

Per operation amortised: $O(\log n)$ .

Worked Example

Starting with 8 singletons: {1}, {2}, {3}, {4}, {5}, {6}, {7}, {8}.

Sequence: Union(1,2), Union(3,4), Union(5,6), Union(7,8), Union(1,3), Union(5,7), Union(1,5).

Union	Sets before	Smaller set	Rep updates	Sets after sizes
1,2	{1},{2}	{2} (size 1)	1 update	{1,2}
3,4	{3},{4}	{4} (size 1)	1 update	{3,4}
5,6	{5},{6}	{6} (size 1)	1 update	{5,6}
7,8	{7},{8}	{8} (size 1)	1 update	{7,8}
1,3	{1,2},{3,4}	{3,4} (size 2)	2 updates	{1,2,3,4}
5,7	{5,6},{7,8}	{7,8} (size 2)	2 updates	{5,6,7,8}
1,5	{1,2,3,4},{5,6,7,8}	{5,6,7,8} (size 4)	4 updates	{1,2,3,4,5,6,7,8}

Total representative updates: $1+1+1+1+2+2+4 = 12$ . Worst case per element: $\log_2 8 = 3$ updates (elements 5 and 7 were updated twice; element 8 updated once; each element updated at most 3 times).

Cyclic Doubly Linked List Variation

Using cyclic doubly linked lists, Union becomes $O(1)$ because we can splice at the position of a and b directly (no need to find the end). However, In-Same-Set (Find) now costs $O(n)$ because we must walk around the list. This trades Union speed for Find speed.

Summary

Implementation	MakeSet	Find	Union	Total (m ops on n items)
Flat forest (array)	$O(1)$	$O(1)$	$O(n)$	$O(mn)$
Flat forest (weighted-union)	$O(1)$	$O(1)$	$O(n)$ worst, $O(\log n)$ amortised	$O(m + n \log n)$
Cyclic DLL	$O(1)$	$O(n)$	$O(1)$	$O(mn)$
Hash table	$O(1)$	$O(1)$	$O(n)$	$O(mn)$

The linked-list approach is a stepping stone. The forest representation (next note) with union by rank and path compression achieves effectively constant time per operation.