From d98f46ce647846b0aa30b2e16a30fd4e152a1bf5 Mon Sep 17 00:00:00 2001 From: Carlos Maiolino Date: Thu, 10 Jul 2025 22:55:07 +0200 Subject: Add new code Signed-off-by: Carlos Maiolino --- java/qfind/QuickUnionUF.java | 47 ++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 47 insertions(+) create mode 100644 java/qfind/QuickUnionUF.java (limited to 'java/qfind/QuickUnionUF.java') 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); + } +} -- cgit v1.2.3