Add Disjoint Set (TheAlgorithms#2684)

NimrodRak · web-flow · commit b608657e5042 · 2021-10-24T10:28:21.000+03:00
diff --git a/DataStructures/DisjointSets/DisjointSets.java b/DataStructures/DisjointSets/DisjointSets.java
@@ -0,0 +1,32 @@
+package 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/DataStructures/DisjointSets/Node.java b/DataStructures/DisjointSets/Node.java
@@ -0,0 +1,11 @@
+package 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;
+    }
+}
