WikiGalaxy
Union By Rank in Disjoint Set
Understanding Union By Rank:
Union By Rank is a technique used in Disjoint Set data structures to keep the tree flat, which helps in reducing the time complexity of operations like union and find. The rank is a heuristic used to keep track of the tree height, and while performing union operations, the tree with lesser rank is attached under the root of the tree with a higher rank.
class DisjointSet {
int[] parent, rank;
public DisjointSet(int n) {
parent = new int[n];
rank = new int[n];
for (int i = 0; i < n; i++) {
parent[i] = i;
rank[i] = 0;
}
}
public int find(int u) {
if (u != parent[u]) {
parent[u] = find(parent[u]);
}
return parent[u];
}
public void union(int u, int v) {
int rootU = find(u);
int rootV = find(v);
if (rootU != rootV) {
if (rank[rootU] < rank[rootV]) {
parent[rootU] = rootV;
} else if (rank[rootU] > rank[rootV]) {
parent[rootV] = rootU;
} else {
parent[rootV] = rootU;
rank[rootU]++;
}
}
}
}
Example 1: Basic Union and Find
In this example, we initialize a disjoint set with 5 elements. We perform union operations to connect elements and use find to determine the root of each set.
DisjointSet ds = new DisjointSet(5);
ds.union(0, 1);
ds.union(1, 2);
System.out.println(ds.find(0)); // Output: 0
System.out.println(ds.find(2)); // Output: 0
Example 2: Union By Rank Optimization
This example demonstrates how union by rank optimizes tree height, ensuring efficient find operations. Here, two sets are merged based on their rank.
ds.union(3, 4);
ds.union(2, 3);
System.out.println(ds.find(4)); // Output: 0, as 4 is now connected to the root 0
Example 3: Path Compression
Path compression is another technique used alongside union by rank to flatten the structure of the tree whenever find is called, leading to more efficient operations.
System.out.println(ds.find(3)); // Output: 0, path compression makes future finds faster
Example 4: Handling Multiple Sets
Here, we demonstrate handling multiple disjoint sets and performing unions between them to form larger sets.
DisjointSet ds2 = new DisjointSet(10);
ds2.union(5, 6);
ds2.union(7, 8);
ds2.union(6, 8);
System.out.println(ds2.find(5)); // Output: 5 or 7 depending on rank
System.out.println(ds2.find(8)); // Output: 5 or 7 depending on rank
Example 5: Checking Connected Components
This example checks if two elements belong to the same set, indicating they are connected components.
boolean isConnected = ds2.find(5) == ds2.find(7);
System.out.println(isConnected); // Output: true, since 5 and 7 are connected
