# Different approach Union Find

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.

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
}
}
$$$$


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 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. ;) – Juru Sep 8 '20 at 20:18

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));
}
`
• It was not a joke, it was a terrible mistake. Thanks for your time. – Juru Sep 9 '20 at 0:04