ADT - Disjoint Set

Disjoint set is a data structure that stores elements which are split into one or more disjoint sets, the elements in these sets are non-overlapping. An union-find algorithm performs two main operations to find representative of a disjoint set and to merge disjoint sets to a single set.

Operation

• makeSet(x)
  • Create a new set containing the element x.
• find(x)
  • Return the representative (also known as the “parent” or “root”) of the set that contains the element x. This operation is used to determine which set an element belongs to.
• union(x, y)
  • Merge the sets containing elements x and y into a single set.

Performance optimisation

Union by rank

Implementation

public class UnionFind() {
	public UnionFind(int size) {
		// initialise the parent array with each element 
		// as its own representative
		private int[] parent;
		for (int i=0; i<size; i++) {
			parent[i] = i;
		}
	}
	
	// find the representative of i
	public int find(int i) {
		if (parent[i] == i) {
			return i;
		}
		// path compression by setting parent[i] to the root of i in each 
		// recursive call
		parent[i] = find(parent[i]);
		return parent[i];
	}
	
	public void union(int i; int j) {
		int iRep = find(i);
		int jRep = find(j);
		parent[iRep] = jRep;
	}
}

public static void main(String[] args) {
	int size = 5;
	UnionFind uf = new UnionFind(size);
	uf.union(1, 2);
	uf.union(3, 4);
}

---

Back to parent page: Data Structures and Algorithms

Reference:

• https://www.geeksforgeeks.org/disjoint-set-data-structures/
• https://www.geeksforgeeks.org/introduction-to-disjoint-set-data-structure-or-union-find-algorithm/