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/WeightedQuickUnionUF.java | 62 ++++++++++++++++++++++++++++++++++++ 1 file changed, 62 insertions(+) create mode 100644 java/qfind/WeightedQuickUnionUF.java (limited to 'java/qfind/WeightedQuickUnionUF.java') diff --git a/java/qfind/WeightedQuickUnionUF.java b/java/qfind/WeightedQuickUnionUF.java new file mode 100644 index 0000000..45f8ba7 --- /dev/null +++ b/java/qfind/WeightedQuickUnionUF.java @@ -0,0 +1,62 @@ +/* + * Weighted Quick Union algorithm + * + * Adds weight to the quick union. + * + * Find: Check if p and q have the same root + * + * Union. Merge trees, but the merge is done depending on the size of each tree. + * The smaller one will be merged into the larger one. + * + * The downside is we need to keep a new extra array to keep track of the + * number of elements on each node. + * + */ + +public class WeightedQuickUnionUF { + private int[] id; + private int[] sz; + + /* Constructor */ + public WeightedQuickUnionUF(int N) { + id = new int[N]; + sz = new int[N]; + + for (int i = 0; i < N; i++) + id[i] = i; + + /* Every node starts with a single item, itself */ + for (int i = 0; i < N; i++) + sz[i] = 1; + } + + /* Return root of 'i' */ + private int root(int i) { + while (i != id[i]) { + /* Compress paths, by pointing the current node to the + * root of its parent */ + id[i] = id[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); + int qroot = root(q); + + if (sz[proot] < sz[qroot]) { + id[proot] = qroot; + sz[proot] += sz[qroot]; + } else { + id[qroot] = proot; + sz[qroot] += sz[proot]; + } + } +} -- cgit v1.2.3