TheAlgorithms · BamaCharanChhandogi · Sep 10, 2023 · Sep 10, 2023 · Sep 10, 2023 · Sep 10, 2023
@@ -0,0 +1,53 @@
+package com.thealgorithms.datastructures.disjointsetunion;
+
+/**
+ * Disjoint Set Union or DSU is useful for solving problems related to connected components,
+ * cycle detection in graphs, and maintaining relationships in disjoint sets of data.
+ * It is commonly employed in graph algorithms and problems.
+ *
+ * @see <a href="https://en.wikipedia.org/wiki/Disjoint-set_data_structure">Disjoint Set Union</a>
+ */
+public class DisjointSetUnion<T> {
+
+    /**
+     * Creates a new node of DSU with parent initialised as same node
+     */
+    public Node<T> makeSet(final T x) {
+        return new Node<T>(x);
+    }
+
+    /**
+     * Finds and returns the representative (root) element of the set to which a given element belongs.
+     * This operation uses path compression to optimize future findSet operations.
+     */
+    public Node<T> findSet(Node<T> node) {
+        while (node != node.parent) {
+            node = node.parent;
+        }
+        return node;
+    }
+
+    /**
+     * Unions two sets by merging their representative elements. The merge is performed based on the rank of each set
+     * to ensure efficient merging and path compression to optimize future findSet operations.
+     */
+    public void unionSets(final Node<T> x, final Node<T> y) {
+        Node<T> nx = findSet(x);
+        Node<T> ny = findSet(y);
+
+        if (nx == ny) {
+            return; // Both elements already belong to the same set.
+        }
+        // Merging happens based on rank of node, this is done to avoid long chaining of nodes and reduce time
+        // to find root of the component. Idea is to attach small components in big, instead of other way around.
+        if (nx.rank > ny.rank) {
+            ny.parent = nx;
+        } else if (ny.rank > nx.rank) {
+            nx.parent = ny;
+        } else {
+            // Both sets have the same rank; choose one as the parent and increment the rank.
+            ny.parent = nx;
+            nx.rank++;
+        }
+    }
+}
@@ -0,0 +1,25 @@
+package com.thealgorithms.datastructures.disjointsetunion;
+
+public class Node<T> {
+
+    /**
+     * The rank of the node, used for optimizing union operations.
+     */
+    public int rank;
+
+    /**
+     * Reference to the parent node in the set.
+     * Initially, a node is its own parent (represents a singleton set).
+     */
+    public Node<T> parent;
+
+    /**
+     * The data element associated with the node.
+     */
+    public T data;
+
+    public Node(final T data) {
+        this.data = data;
+        parent = this; // Initially, a node is its own parent.
+    }
+}
@@ -0,0 +1,51 @@
+package com.thealgorithms.datastructures.disjointsetunion;
+
+import static org.junit.jupiter.api.Assertions.assertNotNull;
+
+import org.junit.jupiter.api.Assertions;
+import org.junit.jupiter.api.Test;
+
+public class DisjointSetUnionTest {
+
+    @Test
+    public void testMakeSet() {
+        DisjointSetUnion<Integer> dsu = new DisjointSetUnion<>();
+        Node<Integer> node = dsu.makeSet(1);
+        assertNotNull(node);
+        Assertions.assertEquals(node, node.parent);
+    }
+
+    @Test
+    public void testUnionFindSet() {
+        DisjointSetUnion<Integer> dsu = new DisjointSetUnion<>();
+        Node<Integer> node1 = dsu.makeSet(1);
+        Node<Integer> node2 = dsu.makeSet(2);
+        Node<Integer> node3 = dsu.makeSet(3);
+        Node<Integer> node4 = dsu.makeSet(4);
+
+        dsu.unionSets(node1, node2);
+        dsu.unionSets(node3, node2);
+        dsu.unionSets(node3, node4);
+        dsu.unionSets(node1, node3);
+
+        Node<Integer> root1 = dsu.findSet(node1);
+        Node<Integer> root2 = dsu.findSet(node2);
+        Node<Integer> root3 = dsu.findSet(node3);
+        Node<Integer> root4 = dsu.findSet(node4);
+
+        Assertions.assertEquals(node1, node1.parent);
+        Assertions.assertEquals(node1, node2.parent);
+        Assertions.assertEquals(node1, node3.parent);
+        Assertions.assertEquals(node1, node4.parent);
+
+        Assertions.assertEquals(node1, root1);
+        Assertions.assertEquals(node1, root2);
+        Assertions.assertEquals(node1, root3);
+        Assertions.assertEquals(node1, root4);
+
+        Assertions.assertEquals(1, node1.rank);
+        Assertions.assertEquals(0, node2.rank);
+        Assertions.assertEquals(0, node3.rank);
+        Assertions.assertEquals(0, node4.rank);
+    }
+}