Repository: TheAlgorithms/Java
Pull request #4366 (2023-09-10 12:33:49)

Enhancing DisjointSetUnion data structure
<!-- For completed items, change [ ] to [x] -->

- [x] I have read [CONTRIBUTING.md](https://github.com/TheAlgorithms/Java/blob/master/CONTRIBUTING.md).
- [x] This pull request is all my own work -- I have not plagiarized it.
- [x] All filenames are in PascalCase.
- [x] All functions and variable names follow Java naming conventions.
- [x] All new algorithms have a URL in their comments that points to Wikipedia or other similar explanations.

Done enhancing of DisjoinSetUnion data structure code, added comments , unit testcase and updated method name. Also updated package name to disjointsets -> disjointsetunion .
<img width="1512" alt="Screenshot 2023-09-10 at 5 56 30 PM" src="https://github.com/TheAlgorithms/Java/assets/76104205/b8208630-f51a-448d-9bb4-f004f2f075bb">



Manan-09: Please help with this lint error , what I need to do ? 

```
@@ -22,4 +22,4 @@
         this.data = data;
         parent = this; // Initially, a node is its own parent.
     }
-}+}
--- ./src/main/java/com/thealgorithms/datastructures/disjointsetunion/DisjointSetUnion.java	(original)
+++ ./src/main/java/com/thealgorithms/datastructures/disjointsetunion/DisjointSetUnion.java	(reformatted)
@@ -50,4 +50,4 @@
             nx.rank++;
         }
     }
-}+}
```

BamaCharanChhandogi: You have to give one space before the curly bracket.
BamaCharanChhandogi: > Please help with this lint error , what I need to do ?
> 
> ```
> @@ -22,4 +22,4 @@
>          this.data = data;
>          parent = this; // Initially, a node is its own parent.
>      }
> -}+}
> --- ./src/main/java/com/thealgorithms/datastructures/disjointsetunion/DisjointSetUnion.java	(original)
> +++ ./src/main/java/com/thealgorithms/datastructures/disjointsetunion/DisjointSetUnion.java	(reformatted)
> @@ -50,4 +50,4 @@
>              nx.rank++;
>          }
>      }
> -}+}
> ```

You have to give one space before the curly bracket.

Manan-09: Thanks @BamaCharanChhandogi 
Manan-09: > Some quick remarks form my side.
> 
> When I will find some nice test covering the missing lines, I will put it here know.
<img width="777" alt="Screenshot 2023-09-10 at 9 38 14 PM" src="https://github.com/TheAlgorithms/Java/assets/76104205/546458b7-af67-49c1-a423-3e025c052fae">
@vil02  Updated testcases, covering all if branches


Patch:
diff --git a/src/main/java/com/thealgorithms/datastructures/disjointsets/DisjointSets.java b/src/main/java/com/thealgorithms/datastructures/disjointsets/DisjointSets.java
deleted file mode 100644
index cf26fce7..00000000
--- a/src/main/java/com/thealgorithms/datastructures/disjointsets/DisjointSets.java
+++ /dev/null
@@ -1,33 +0,0 @@
-package com.thealgorithms.datastructures.disjointsets;
-
-public class DisjointSets<T> {
-
-    public Node<T> MakeSet(T x) {
-        return new Node<T>(x);
-    }
-
-    public Node<T> FindSet(Node<T> node) {
-        if (node != node.parent) {
-            node.parent = FindSet(node.parent);
-        }
-
-        return node.parent;
-    }
-
-    public void UnionSet(Node<T> x, Node<T> y) {
-        Node<T> nx = FindSet(x);
-        Node<T> ny = FindSet(y);
-
-        if (nx == ny) {
-            return;
-        }
-        if (nx.rank > ny.rank) {
-            ny.parent = nx;
-        } else if (ny.rank > nx.rank) {
-            nx.parent = ny;
-        } else {
-            nx.parent = ny;
-            ny.rank++;
-        }
-    }
-}
diff --git a/src/main/java/com/thealgorithms/datastructures/disjointsets/Node.java b/src/main/java/com/thealgorithms/datastructures/disjointsets/Node.java
deleted file mode 100644
index f2054331..00000000
--- a/src/main/java/com/thealgorithms/datastructures/disjointsets/Node.java
+++ /dev/null
@@ -1,13 +0,0 @@
-package com.thealgorithms.datastructures.disjointsets;
-
-public class Node<T> {
-
-    public int rank;
-    public Node<T> parent;
-    public T data;
-
-    public Node(T data) {
-        this.data = data;
-        parent = this;
-    }
-}
diff --git a/src/main/java/com/thealgorithms/datastructures/disjointsetunion/DisjointSetUnion.java b/src/main/java/com/thealgorithms/datastructures/disjointsetunion/DisjointSetUnion.java
new file mode 100644
index 00000000..58380099
--- /dev/null
+++ b/src/main/java/com/thealgorithms/datastructures/disjointsetunion/DisjointSetUnion.java
@@ -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++;
+        }
+    }
+}
diff --git a/src/main/java/com/thealgorithms/datastructures/disjointsetunion/Node.java b/src/main/java/com/thealgorithms/datastructures/disjointsetunion/Node.java
new file mode 100644
index 00000000..260f297b
--- /dev/null
+++ b/src/main/java/com/thealgorithms/datastructures/disjointsetunion/Node.java
@@ -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.
+    }
+}


Test patch:
diff --git a/src/test/java/com/thealgorithms/datastructures/disjointsetunion/DisjointSetUnionTest.java b/src/test/java/com/thealgorithms/datastructures/disjointsetunion/DisjointSetUnionTest.java
new file mode 100644
index 00000000..a10a99d4
--- /dev/null
+++ b/src/test/java/com/thealgorithms/datastructures/disjointsetunion/DisjointSetUnionTest.java
@@ -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);
+    }
+}