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.