Add new code

Signed-off-by: Carlos Maiolino <[email protected]>

1 files changed, 47 insertions, 0 deletions

diff --git a/java/qfind/QuickUnionUF.java b/java/qfind/QuickUnionUF.java
new file mode 100644
index 0000000..aab4fb4
--- /dev/null
+++ b/java/qfind/QuickUnionUF.java
@@ -0,0 +1,47 @@
+/*
+ * Quick Union algorithm
+ *
+ * Slightly better than quickfind
+ *
+ * treats each element in the array as a node in a tree and trees may be
+ * connected together or not. Essentially each element might be its own tree.
+ *
+ * Find: Check if p and q have the same root
+ *
+ * Union. Merge components containing p and q, set the id of p's root to the id
+ * of q's root.
+ *
+ * Still too slow though. Trees can get too tall, where the worst case is a tree
+ * where one element points to a single one until the end of the tree,
+ * essentially creating an array.
+ */
+
+public class QuickUnionUF {
+	private int[] id;
+
+	/* Constructor */
+	public QuickUnionUF(int N) {
+		id = new int[N];
+
+		for (int i = 0; i < N; i++)
+			id[i] = i;
+	}
+
+	/* Return root of 'i' */
+	private int root(int i) {
+		while (i != id[i])
+			i = id[i];
+		return i;
+	}
+
+	/* Are the objects connected */
+	public boolean connected(int p, int q) {
+		return root(p) == root(q);
+	}
+
+	/* Connect two objects */
+	public void union(int p, int q) {
+		int proot = root(p);
+		id[proot] = root(q);
+	}
+}