Add UnionFind implementation

Lord-of-Algorithms · Lord-of-Algorithms · commit da9b5863e5ff · 2024-07-21T19:23:14.000+03:00
diff --git a/src/unionfind/UnionFind.java b/src/unionfind/UnionFind.java
@@ -0,0 +1,73 @@
+package unionfind;
+
+/**
+ * Implements the union-find data structure (also known as disjoint-set).
+ * This implementation uses path compression in the find operation.
+ */
+public class UnionFind {
+
+    private static class Set {
+        // the parent index of the element
+        int parent;
+        int rank;
+
+        Set(int parent, int rank) {
+            this.parent = parent;
+            this.rank = rank;
+        }
+    }
+
+    private final Set[] sets;
+
+    /**
+     * Initializes the UnionFind structure with a specified number of elements.
+     * Each element is initially in its own set.
+     */
+    public UnionFind(int count) {
+        sets = new Set[count];
+        for (int i = 0; i < count; i++) {
+            sets[i] = new Set(i, 0);
+        }
+    }
+
+    /**
+     * Finds the representative (root) of the set containing 'element'
+     * and applies path compression.
+     *
+     * @return the representative of the set containing 'element'
+     */
+    public int find(int element) {
+        if (element < 0 || element >= sets.length) {
+            throw new IllegalArgumentException("Element out of bounds");
+        }
+        if (sets[element].parent != element)
+            sets[element].parent = find(sets[element].parent);
+        return sets[element].parent;
+    }
+
+    /**
+     * Merges the sets containing elements 'x' and 'y'.
+     *
+     * @param x an element of the first set
+     * @param y an element of the second set
+     */
+    public void union(int x, int y) {
+        if (x < 0 || x >= sets.length || y < 0 || y >= sets.length) {
+            throw new IllegalArgumentException("Element out of bounds");
+        }
+
+        int xRoot = find(x);
+        int yRoot = find(y);
+
+        if (xRoot != yRoot) {
+            if (sets[xRoot].rank < sets[yRoot].rank) {
+                sets[xRoot].parent = yRoot;
+            } else if (sets[xRoot].rank > sets[yRoot].rank) {
+                sets[yRoot].parent = xRoot;
+            } else {
+                sets[yRoot].parent = xRoot;
+                sets[xRoot].rank++;
+            }
+        }
+    }
+}
diff --git a/src/unionfind/UnionFindMain.java b/src/unionfind/UnionFindMain.java
@@ -0,0 +1,35 @@
+package unionfind;
+
+public class UnionFindMain {
+    public static void main(String[] args) {
+        // Initialize UnionFind with 10 elements
+        UnionFind uf = new UnionFind(10);
+
+        // Perform some union operations
+        uf.union(0, 1);
+        uf.union(2, 3);
+        uf.union(4, 5);
+        uf.union(6, 7);
+        uf.union(7, 8);
+        uf.union(0, 9);
+        uf.union(5, 9);
+
+        // Output the root of each element to show which set they belong to
+        for (int i = 0; i < 10; i++) {
+            System.out.println("Element " + i + " is in set: " + uf.find(i));
+        }
+
+        // Check if two elements are in the same set
+        int setX = uf.find(2);
+        int setY = uf.find(3);
+        System.out.println("Elements 2 and 3 are in the same set: " + (setX == setY));
+
+        setX = uf.find(0);
+        setY = uf.find(8);
+        System.out.println("Elements 0 and 8 are in the same set: " + (setX == setY));
+
+        setX = uf.find(1);
+        setY = uf.find(6);
+        System.out.println("Elements 1 and 6 are in the same set: " + (setX == setY));
+    }
+}
