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

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.

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));
    }