ChandanChainani · February 19, 2023 16:42 · Jul 7, 2019 · May 16, 2019 · May 15, 2019
diff --git a/dsu.js b/dsu.js
@@ -42,6 +42,9 @@ class DSU {
 			// all of those nodes are now also connected to x's parent.
 			this.parents[xpar]+=this.parents[ypar]; 
 			this.parents[ypar]=xpar;
+			return false;
+		} else {
+			return true; //this link creates a cycle
 		}
 	}
 	console_print() {

diff --git a/dsu.js b/dsu.js
@@ -0,0 +1,70 @@
+// https://www.youtube.com/watch?v=wU6udHRIkcc
+
+/*
+Disjoint Set Union (“DSU”)  is the Data Structure: disjoint-set data structure 
+is a data structure that keeps track of a set of elements partitioned into a 
+number of disjoint (non-overlapping) subsets.
+
+Union Find is the Algorithm: A union-find algorithm is an algorithm that can 
+be used to detect cycles in an undirected graph & performs two useful operations
+ on such a data structure:
+ 
+1) Find: Determine which subset a particular element is in. This can be used 
+for determining if two elements are in the same subset.
+
+2) Union: Join two subsets into a single subset.
+*/
+
+class DSU {
+	constructor() {
+		this.parents = [];
+	}
+	find(x) {
+		if(typeof this.parents[x] != "undefined") {
+			if(this.parents[x]<0) {
+				return x; //x is a parent
+			} else {
+				//recurse until you find x's parent
+				return this.find(this.parents[x]);
+			}
+		} else {
+			// initialize this node to it's on parent (-1)
+			this.parents[x]=-1;
+			return x; //return the index of the parent
+		}
+	}
+	union(x,y) {
+		var xpar = this.find(x);
+		var ypar = this.find(y);
+		if(xpar != ypar) {
+			// x's parent is now the parent of y also. 
+			// if y was a parent to more than one node, then
+			// all of those nodes are now also connected to x's parent.
+			this.parents[xpar]+=this.parents[ypar]; 
+			this.parents[ypar]=xpar;
+		}
+	}
+	console_print() {
+		console.log(this.parents);
+	}
+}
+
+var dsu = new DSU();
+dsu.union(1,2);
+dsu.console_print();
+dsu.union(3,4);
+dsu.console_print();
+dsu.union(5,6);
+dsu.console_print();
+dsu.union(7,8);
+dsu.console_print();
+dsu.union(2,4);
+dsu.console_print();
+dsu.union(2,5);
+dsu.console_print();
+dsu.union(1,3);
+dsu.console_print();
+dsu.union(6,8);
+dsu.console_print();
+dsu.union(5,7);
+dsu.console_print();