WikiGalaxy
Find Operations in Disjoint Set ADT
Introduction
The Find operation in Disjoint Set Abstract Data Type (ADT) is crucial for determining the representative of the set containing a particular element. It assists in checking if two elements are in the same set and is often used in union-find algorithms.
Example 1: Basic Find Operation
class DisjointSet {
int[] parent;
public DisjointSet(int n) {
parent = new int[n];
for (int i = 0; i < n; i++) {
parent[i] = i;
}
}
public int find(int x) {
if (parent[x] != x) {
return find(parent[x]);
}
return x;
}
}
Explanation
In this basic implementation, the find operation recursively traverses the parent array until it finds the root of the set. This root is the representative of the set.
Example 2: Find with Path Compression
class DisjointSet {
int[] parent;
public DisjointSet(int n) {
parent = new int[n];
for (int i = 0; i < n; i++) {
parent[i] = i;
}
}
public int find(int x) {
if (parent[x] != x) {
parent[x] = find(parent[x]);
}
return parent[x];
}
}
Explanation
Path compression is an optimization that flattens the structure of the tree whenever find is called, making future queries faster by directly linking nodes to the root.
Example 3: Find in Union by 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 x) {
if (parent[x] != x) {
parent[x] = find(parent[x]);
}
return parent[x];
}
}
Explanation
In union by rank, the tree with the smaller rank is attached under the root of the tree with the larger rank. The find operation remains the same but benefits from the balanced trees created by union by rank.
Example 4: Find with Union by Size
class DisjointSet {
int[] parent, 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];
}
}
Explanation
Union by size attaches the smaller tree under the larger tree, which helps in keeping the trees shallow. The find operation benefits from this as it reduces the path length.
Example 5: Iterative Find
class DisjointSet {
int[] parent;
public DisjointSet(int n) {
parent = new int[n];
for (int i = 0; i < n; i++) {
parent[i] = i;
}
}
public int find(int x) {
while (parent[x] != x) {
x = parent[x];
}
return x;
}
}
Explanation
This example demonstrates an iterative approach to the find operation, which avoids recursion and may be preferred in environments with limited stack space.
