Add new code

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

1 files changed, 39 insertions, 0 deletions

diff --git a/java/qfind/QuickFindUF.java b/java/qfind/QuickFindUF.java
new file mode 100644
index 0000000..4018515
--- /dev/null
+++ b/java/qfind/QuickFindUF.java
@@ -0,0 +1,39 @@
+/*
+ * Quick Find algorithm
+ *
+ * Very slow as it uses N^2 time as it needs to access the whole array twice.
+ *
+ * If we have a 10^9 union commands on 10^9 objects, we'll need 10^18 operations
+ * to actually finish the algorithm.
+ * 30+ years of computer time.
+ *
+ * Quadratic algorithms don't scale with technology.
+ */
+
+public class QuickFindUF {
+	private int[] id;
+
+	/* Constructor */
+	public QuickFindUF(int N) {
+		id = new int[N];
+
+		for (int i = 0; i < N; i++)
+			id[i] = i;
+	}
+
+	/* Are the objects connected */
+	public boolean connected(int p, int q) {
+		return id[p] == id[q];
+	}
+
+	/* Connect two objects */
+	public void union(int p, int q) {
+		int pid = id[p];
+		int qid = id[q];
+
+		for (int i = 0; i < id.length; i++) {
+			if (id[i] == pid)
+				id[i] = qid;
+		}
+	}
+}