Different approach Union Find

Question

I am studying algorithms and I did this "Union Find Like" algorithm.

I have one array of objects with a reference and I make the union pointing to the same reference instead of have two int[] with numbers and weights.

• Its not necessary to initialize the array.
• You will have a maximum of N/2 extra objects ( if you do a union in pairs ), but in an array with a lot of unions you will have just a few objects (only the R roots) with only references pointing to the same object.
• It's a linear time.

Can I have some feedback about this idea?

Thanks.

public class UnionFind {
 
 public static class Pointer {
 Pointer pointerForJoin;
 }
 
 
 // number of elements in array
 private static final int N = 10;
 private static Pointer[] connection = new Pointer[N];
 
 private static void union(int a, int b) {
 if(connection[a] != null && connection[b] != null) {
 if(connection[a].pointerForJoin != connection[b].pointerForJoin )
 connection[a].pointerForJoin = connection[b].pointerForJoin = connection[a]; 
 } else if(connection[a] != null) {
 connection[b] = connection[a];
 } else if(connection[b] != null) {
 connection[a] = connection[b];
 } else {
 connection[a] = connection[b] = new Pointer();
 connection[a].pointerForJoin = connection[b].pointerForJoin = connection[a]; 
 }
 }
 
 private static boolean isConnected(int a, int b) {
 if (a == b) return true;
 if(connection[a] == null || connection[b] == null) return false;
 return connection[a].pointerForJoin == connection[b].pointerForJoin;
 }
 
 public static void main(String[] args) { 
 union(1,2);
 union(2,3);
 union(5,6);
 union(8,9);
 union(8,2);
 
 System.out.println(isConnected(8,3)); //true
 System.out.println(isConnected(8,2)); //true
 System.out.println(isConnected(9,1)); //true
 System.out.println(isConnected(1,6)); //false
 System.out.println(isConnected(1,7)); //false
 System.out.println(isConnected(0,0)); //true
 }
}
```

• pacmaninbw: Please do not edit the question especially the code after an answer has been posted, because all reviewers/answerers need to be able to see the same code. Read what to do or not to do when your question is answered.

Answer 1

First of all, I like the idea and the implementation.

I have refactored it a bit and came up with that:

isConnected: Extract connection[a] and connection[b] in local variables and simplify the condition. Eclipse can assist you with the first step, the second one I did manually.

 private static boolean isConnected(int a, int b) {
 if (a == b) {
 return true;
 } else {
 final var pa = connection[a];
 final var pb = connection[b];
 return pa != null && pb != null && pa.pointerForJoin == pb.pointerForJoin;
 }
 }

In union I did the same with the local variables (beware of the assignments in the array. Then I used nested IFs, which make the program flow easier to read.

This results in:

private static void union(int a, int b) {
 final var pa = connection[a];
 final var pb = connection[b];
 if(pa != null) {
 if (pb != null) {
 if(pa.pointerForJoin != pb.pointerForJoin)
 pa.pointerForJoin = pb.pointerForJoin = pa;
 } else {
 connection[b] = pa;
 }
 } else {
 // pa == null
 if(pb != null) {
 connection[a] = pb;
 } else {
 connection[a] = connection[b] = new Pointer();
 connection[a].pointerForJoin = connection[a];
 }
 }
}

The next step is to use a helper class instead of static variables, like that:

public class UnionFind {
 
 public static class Pointer {
 Pointer pointerForJoin;
 }
 
 private final Pointer[] connection;
 
 public UnionFind(int n) {
 connection = new Pointer[n];
 }
 
 private void union(int a, int b) {
 final var pa = connection[a];
 final var pb = connection[b];
 if(pa != null) {
 if (pb != null) {
 if(pa.pointerForJoin != pb.pointerForJoin)
 pa.pointerForJoin = pb.pointerForJoin = pa;
 } else {
 connection[b] = pa;
 }
 } else {
 // pa == null
 if(pb != null) {
 connection[a] = pb;
 } else {
 connection[a] = connection[b] = new Pointer();
 connection[a].pointerForJoin = connection[a];
 }
 }
 }
 
 private boolean isConnected(int a, int b) {
 if (a == b) {
 return true;
 } else {
 final var pa = connection[a];
 final var pb = connection[b];
 return pa != null && pb != null && pa.pointerForJoin == pb.pointerForJoin;
 }
 }
 
 public static void main(String[] args) {
 var uf = new UnionFind(10);
 uf.union(1,2);
 uf.union(2,3);
 uf.union(5,6);
 uf.union(8,9);
 uf.union(8,2);
 
 System.out.println(uf.isConnected(8,3)); //true
 System.out.println(uf.isConnected(8,2)); //true
 System.out.println(uf.isConnected(9,1)); //true
 System.out.println(uf.isConnected(1,6)); //false
 System.out.println(uf.isConnected(1,7)); //false
 System.out.println(uf.isConnected(0,0)); //true
 }
}

You see how you can create multiple instances of UnionFind? You can even set a capacity at runtime.

I will leave the addition of the missing JavaDoc to you.

• Juru: I was trying to make a proof of concept of an alternative way (maybe better?) to implement Union Find and I didnt worry about refactoring the code before send it. I should have done that. Thanks for your feedback I will make the changes. ;)

Answer 2

As soon as you said it's linear time, it was clear that something is wrong. Quick glance at the code showed no loops or recursion, so it was clear that it's indeed linear time and that your algorithm doesn't work.

Here's an example you fail, you report false even though 3 and 5 should be connected due to union(3,1) and union(1,5):

 public static void main(String[] args) { 
 union(1,2);
 union(3,4);
 union(5,6);
 union(3,1);
 union(1,5);
 
 System.out.println(isConnected(3,5));
 }

• Juru: It was not a joke, it was a terrible mistake. Thanks for your time.