# 1. Introduction

The *Union-Find* data structure, also known as the *Disjoint Set* data structure, provides an efficient way to handle the union and find operations on disjoint sets. It has applications in various domains, including graph theory, where it can be used to determine if adding an edge would create a cycle. This post presents an implementation of the Union-Find data structure in Java.

# 2. Program Steps

1. Create an array *parent* where each index represents a set and its value is the index of its parent.

2. Create another array *rank* to keep track of the depth of trees.

3. Implement *find(int x)* to determine which set a particular element belongs to. This involves following parent pointers until reaching the root of the tree.

4. Implement *union(int x, int y)* to join two sets together. This uses the rank array to ensure the tree remains balanced.

5. Implement path compression in the *find* method for better efficiency.

# 3. Code Program

```
class UnionFind {
private int[] parent;
private int[] rank;
public UnionFind(int size) {
parent = new int[size];
rank = new int[size];
for (int i = 0; i < size; i++) {
parent[i] = i;
rank[i] = 1;
}
}
public int find(int x) {
if (parent[x] != x) {
parent[x] = find(parent[x]); // Path compression
}
return parent[x];
}
public boolean union(int x, int y) {
int rootX = find(x);
int rootY = find(y);
if (rootX == rootY) {
return false; // They are already in the same set
}
if (rank[rootX] < rank[rootY]) {
parent[rootX] = rootY;
} else if (rank[rootX] > rank[rootY]) {
parent[rootY] = rootX;
} else {
parent[rootY] = rootX;
rank[rootX]++;
}
return true;
}
public static void main(String[] args) {
UnionFind uf = new UnionFind(5);
System.out.println(uf.union(0, 1));
System.out.println(uf.union(1, 2));
System.out.println(uf.union(2, 3));
System.out.println(uf.union(3, 4));
System.out.println(uf.union(0, 4));
System.out.println(uf.union(0, 2));
}
}
```

### Output:

true true true true true false

# 4. Step By Step Explanation

1. We start by initializing two arrays, *parent* and *rank*. Every element is its own parent at the beginning, and the rank of every set is initially 1.

2. The *find* method returns the parent of an element. Using path compression, it ensures that each element points directly to the root of its set, thereby flattening the tree structure and speeding up future operations.

3. The *union* method joins two sets together. It first finds the roots of the sets to which *x* and *y* belong. If they have the same root, they are already in the same set. Otherwise, the root with the smaller rank is attached to the root with the larger rank. If they have the same rank, choose one root arbitrarily, increment its rank, and attach the other root to it.

4. In the *main* method, we test the Union-Find structure. We first join sets together and print the result of the union operation. After several unions, when we try to unite elements from the same set, the union method returns *false*, indicating they are already in the same set.