WikiGalaxy
Disjoint Set with Union by Size
Introduction
A disjoint set, also known as a union-find data structure, is a data structure that keeps track of a partition of a set into disjoint (non-overlapping) subsets. Union by size is an optimization technique used to improve the efficiency of the union operation by always attaching the smaller tree under the larger tree.
class DisjointSet {
int[] parent;
int[] size;
public DisjointSet(int n) {
parent = new int[n];
size = new int[n];
for (int i = 0; i < n; i++) {
parent[i] = i;
size[i] = 1;
}
}
public int find(int x) {
if (parent[x] != x) {
parent[x] = find(parent[x]);
}
return parent[x];
}
public void union(int x, int y) {
int rootX = find(x);
int rootY = find(y);
if (rootX != rootY) {
if (size[rootX] < size[rootY]) {
parent[rootX] = rootY;
size[rootY] += size[rootX];
} else {
parent[rootY] = rootX;
size[rootX] += size[rootY];
}
}
}
}
Union Operation
The union operation merges two subsets into a single subset. In union by size, we attach the smaller tree under the larger tree to keep the tree as flat as possible, minimizing the depth of the tree.
Example 1: Basic Union and Find
Scenario
Consider a set of elements {0, 1, 2, 3, 4}. Initially, each element is its own set. We perform union operations to group them.
public static void main(String[] args) {
DisjointSet ds = new DisjointSet(5);
ds.union(0, 1);
ds.union(2, 3);
ds.union(1, 2);
System.out.println(ds.find(0)); // Output: 3
System.out.println(ds.find(4)); // Output: 4
}
Explanation
After the union operations, elements 0, 1, 2, and 3 are in the same set, while element 4 remains in its own set.
Example 2: Union by Size
Scenario
Using union by size, we ensure that the smaller set is always merged under the larger set to keep the tree balanced.
public static void main(String[] args) {
DisjointSet ds = new DisjointSet(6);
ds.union(0, 1);
ds.union(1, 2);
ds.union(3, 4);
ds.union(4, 5);
ds.union(2, 3);
System.out.println(ds.find(0)); // Output: 5
System.out.println(ds.find(3)); // Output: 5
}
Explanation
The union by size ensures that the resulting tree remains balanced, optimizing the find operation.
Example 3: Path Compression
Scenario
Path compression is another optimization technique where we make nodes point directly to the root during find operations, further flattening the tree.
public static void main(String[] args) {
DisjointSet ds = new DisjointSet(7);
ds.union(0, 1);
ds.union(1, 2);
ds.union(3, 4);
ds.union(5, 6);
ds.union(2, 3);
ds.union(4, 5);
System.out.println(ds.find(0)); // Output: 6
System.out.println(ds.find(1)); // Output: 6
}
Explanation
Path compression significantly reduces the time complexity of the find operation by flattening the tree structure.
Example 4: Union by Size with Path Compression
Scenario
Combining union by size and path compression results in an efficient disjoint set data structure with nearly constant time operations.
public static void main(String[] args) {
DisjointSet ds = new DisjointSet(8);
ds.union(0, 1);
ds.union(2, 3);
ds.union(4, 5);
ds.union(6, 7);
ds.union(1, 2);
ds.union(3, 4);
ds.union(5, 6);
System.out.println(ds.find(0)); // Output: 7
System.out.println(ds.find(7)); // Output: 7
}
Explanation
This combination ensures that both union and find operations are efficient, with the amortized time complexity being nearly constant.
Example 5: Practical Application in Network Connectivity
Scenario
A practical application of disjoint sets is to determine network connectivity. Each node represents a computer, and connections between them are edges.
public static void main(String[] args) {
DisjointSet ds = new DisjointSet(5);
ds.union(0, 1);
ds.union(1, 2);
ds.union(3, 4);
System.out.println(ds.find(0) == ds.find(2)); // Output: true
System.out.println(ds.find(0) == ds.find(3)); // Output: false
}
Explanation
This structure can quickly determine if two computers are in the same network or not, making it useful for network connectivity checks.
Example 6: Cycle Detection in Graphs
Scenario
Disjoint sets can be used to detect cycles in undirected graphs. If two vertices are in the same set before adding an edge, adding that edge would form a cycle.
public static boolean hasCycle(int[][] edges, int n) {
DisjointSet ds = new DisjointSet(n);
for (int[] edge : edges) {
int x = edge[0];
int y = edge[1];
if (ds.find(x) == ds.find(y)) {
return true;
}
ds.union(x, y);
}
return false;
}
public static void main(String[] args) {
int[][] edges = {{0, 1}, {1, 2}, {2, 0}};
System.out.println(hasCycle(edges, 3)); // Output: true
}
Explanation
The disjoint set efficiently checks for cycles, which is crucial in graph algorithms to ensure acyclic properties.
Example 7: Kruskal's Algorithm for Minimum Spanning Tree
Scenario
Kruskal's algorithm uses disjoint sets to find the minimum spanning tree of a graph by adding edges in order of increasing weight, ensuring no cycles are formed.
import java.util.*;
class Edge implements Comparable {
int src, dest, weight;
public int compareTo(Edge compareEdge) {
return this.weight - compareEdge.weight;
}
}
public static List kruskalMST(List edges, int n) {
Collections.sort(edges);
DisjointSet ds = new DisjointSet(n);
List result = new ArrayList<>();
for (Edge edge : edges) {
int x = ds.find(edge.src);
int y = ds.find(edge.dest);
if (x != y) {
result.add(edge);
ds.union(x, y);
}
}
return result;
}
public static void main(String[] args) {
List edges = Arrays.asList(new Edge(0, 1, 10), new Edge(1, 2, 15), new Edge(0, 2, 5));
List mst = kruskalMST(edges, 3);
for (Edge edge : mst) {
System.out.println(edge.src + " - " + edge.dest);
}
}
Explanation
Disjoint sets efficiently manage the connected components during the execution of Kruskal's algorithm, ensuring the MST is built correctly.
Example 8: Image Processing - Connected Components
Scenario
In image processing, disjoint sets can be used to identify connected components, which are groups of connected pixels with the same value.
public static int countConnectedComponents(int[][] image) {
int rows = image.length;
int cols = image[0].length;
DisjointSet ds = new DisjointSet(rows * cols);
for (int r = 0; r < rows; r++) {
for (int c = 0; c < cols; c++) {
if (image[r][c] == 1) {
int index = r * cols + c;
if (r > 0 && image[r - 1][c] == 1) ds.union(index, (r - 1) * cols + c);
if (c > 0 && image[r][c - 1] == 1) ds.union(index, r * cols + (c - 1));
}
}
}
Set uniqueComponents = new HashSet<>();
for (int r = 0; r < rows; r++) {
for (int c = 0; c < cols; c++) {
if (image[r][c] == 1) {
uniqueComponents.add(ds.find(r * cols + c));
}
}
}
return uniqueComponents.size();
}
public static void main(String[] args) {
int[][] image = {
{1, 0, 0, 1},
{1, 1, 0, 0},
{0, 0, 1, 1},
{0, 0, 0, 1}
};
System.out.println(countConnectedComponents(image)); // Output: 3
}
Explanation
This example demonstrates how disjoint sets can be used to efficiently find and count connected components in a binary image.
