The union operation in a disjoint set (or union-find) data structure is used to merge two distinct sets into a single set. This operation is crucial for efficiently managing and grouping elements in various applications, such as network connectivity, image processing, and more.

Example 1: Basic Union Operation

Basic Concept

In a basic union operation, two sets are combined by linking one root to another. The union operation ensures that the elements of both sets can be accessed via a common root.


public class DisjointSet {
    private int[] parent;

    public DisjointSet(int n) {
        parent = new int[n];
        for (int i = 0; i < n; i++) {
            parent[i] = i;
        }
    }

    public void union(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);
        if (rootX != rootY) {
            parent[rootY] = rootX;
        }
    }

    public int find(int x) {
        if (parent[x] != x) {
            parent[x] = find(parent[x]);
        }
        return parent[x];
    }
}

Console Output:

Set after union(0, 1): [0, 0, 2, 3, 4]

Example 2: Union by Rank

Optimizing Union with Rank

Union by rank is an optimization technique used to keep the tree flat. By attaching the smaller tree under the root of the larger tree, we minimize the height of the trees, leading to more efficient find operations.


public class DisjointSetByRank {
    private int[] parent, rank;

    public DisjointSetByRank(int n) {
        parent = new int[n];
        rank = new int[n];
        for (int i = 0; i < n; i++) {
            parent[i] = i;
            rank[i] = 0;
        }
    }

    public void union(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);
        if (rootX != rootY) {
            if (rank[rootX] < rank[rootY]) {
                parent[rootX] = rootY;
            } else if (rank[rootX] > rank[rootY]) {
                parent[rootY] = rootX;
            } else {
                parent[rootY] = rootX;
                rank[rootX]++;
            }
        }
    }

    public int find(int x) {
        if (parent[x] != x) {
            parent[x] = find(parent[x]);
        }
        return parent[x];
    }
}

Console Output:

Set after union(2, 3) with rank: [0, 0, 2, 2, 4]

Example 3: Path Compression

Enhancing Efficiency with Path Compression

Path compression is another optimization that flattens the structure of the tree whenever find is called. It makes the trees even shallower, ensuring that future operations are faster.


public class DisjointSetWithPathCompression {
    private int[] parent;

    public DisjointSetWithPathCompression(int n) {
        parent = new int[n];
        for (int i = 0; i < n; i++) {
            parent[i] = i;
        }
    }

    public void union(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);
        if (rootX != rootY) {
            parent[rootY] = rootX;
        }
    }

    public int find(int x) {
        if (parent[x] != x) {
            parent[x] = find(parent[x]);
        }
        return parent[x];
    }
}

Console Output:

Set after path compression on find(4): [0, 0, 2, 2, 0]

Example 4: Union by Size

Balancing Trees with Union by Size

Union by size is similar to union by rank but uses the size of the trees instead. This method attaches the smaller tree under the larger tree, which helps in maintaining balanced trees.


public class DisjointSetBySize {
    private int[] parent, size;

    public DisjointSetBySize(int n) {
        parent = new int[n];
        size = new int[n];
        for (int i = 0; i < n; i++) {
            parent[i] = i;
            size[i] = 1;
        }
    }

    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];
            }
        }
    }

    public int find(int x) {
        if (parent[x] != x) {
            parent[x] = find(parent[x]);
        }
        return parent[x];
    }
}

Console Output:

Set after union by size(3, 4): [0, 0, 2, 3, 3]

Example 5: Union-Find Application in Kruskal's Algorithm

Kruskal's Algorithm for Minimum Spanning Tree

Kruskal's algorithm uses the union-find data structure to detect cycles and construct the minimum spanning tree of a graph. By performing union operations, it ensures that the edges added do not form a cycle.


class Edge implements Comparable {
    int src, dest, weight;

    public int compareTo(Edge compareEdge) {
        return this.weight - compareEdge.weight;
    }
}

class Graph {
    int V, E;
    Edge[] edge;

    Graph(int v, int e) {
        V = v;
        E = e;
        edge = new Edge[E];
        for (int i = 0; i < e; ++i)
            edge[i] = new Edge();
    }

    int find(int[] parent, int i) {
        if (parent[i] != i)
            parent[i] = find(parent, parent[i]);
        return parent[i];
    }

    void union(int[] parent, int[] rank, int x, int y) {
        int xroot = find(parent, x);
        int yroot = find(parent, y);
        if (rank[xroot] < rank[yroot])
            parent[xroot] = yroot;
        else if (rank[xroot] > rank[yroot])
            parent[yroot] = xroot;
        else {
            parent[yroot] = xroot;
            rank[xroot]++;
        }
    }

    void KruskalMST() {
        Edge[] result = new Edge[V];
        int e = 0;
        int i = 0;
        for (i = 0; i < V; ++i)
            result[i] = new Edge();

        Arrays.sort(edge);
        int[] parent = new int[V];
        int[] rank = new int[V];
        for (int v = 0; v < V; ++v) {
            parent[v] = v;
            rank[v] = 0;
        }

        i = 0;
        while (e < V - 1) {
            Edge next_edge = edge[i++];
            int x = find(parent, next_edge.src);
            int y = find(parent, next_edge.dest);

            if (x != y) {
                result[e++] = next_edge;
                union(parent, rank, x, y);
            }
        }
    }
}

Console Output:

Edges in the constructed MST