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 : Extrae la conexión [a] y la conexión [b] en variables locales y simplifica la condición. Eclipse puede ayudarlo con el primer paso, el segundo que hice manualmente.

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

En unión hice lo mismo con las variables locales (cuidado con las asignaciones en la matriz. Luego utilicé IF anidados, que facilitan la lectura del flujo del programa.

Esto resulta en:

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

El siguiente paso es usar una clase auxiliar en lugar de variables estáticas, así:

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

¿Ves cómo puedes crear múltiples instancias de UnionFind? Incluso puede establecer una capacidad en tiempo de ejecución.

Te dejaré la adición del JavaDoc que falta.

Answer 2

Tan pronto como dijiste que era tiempo lineal, quedó claro que algo andaba mal. Un vistazo rápido al código no mostró bucles ni recursividad, por lo que estaba claro que de hecho es un tiempo lineal y que su algoritmo no funciona.

Aquí hay un ejemplo en el que falla, informa falsea pesar de que 3y 5debería estar conectado debido a union(3,1)y 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));
    }