Dynamic Connectivity: Union Find

Union Find

QuickFindUF

public class QuickFindUF {
    private int[] id;
    private int count;
    private int len;

    public QuickFindUF(int N) {
        this.id = new int[N];
        this.count = N;
        this.len = N;

        for (int i = 0; i < N; i++) {
            this.id[i] = i;
        }
    }

    int find(int p) {
        return this.id[p];
    }

    void union(int p, int q) {
        this.validate(p);
        this.validate(q);

        int pid = this.find(p);
        int qid = this.find(q);

        if (pid == qid) return;

        for (int i = 0; i < this.len; i++)
            if (this.id[i] == pid)
                this.id[i] = qid;
        this.count--;
    }

    void validate(int p) {
        if (p < 0 || p > this.len - 1) {
            throw new IllegalArgumentException(
                    p + " is not between " + 0 + " and " + (this.len - 1));
        }
    }

    public static void main(String[] args) {
        System.out.println("test");

    }

}

QuickUnionUF

ublic class QuickUnionUF {
    private int[] parents;
    private int count;
    private int size;

    public QuickUnionUF(int N) {
        this.parents = new int[N];
        this.count = N;
        this.size = N;
        for (int i = 0; i < N; i++) {
            parents[i] = i;
        }
    }

    void validate(int p) {
        if (p < 0 || p > this.size - 1) {
            throw new IllegalArgumentException(
                    p + " is not between " + 0 + " and " + (this.size - 1));
        }
    }

    int find(int p) {
        this.validate(p);
        while (p != this.parents[p]) p = this.parents[p];
        return p;
    }

    void union(int p, int q) {
        this.validate(p);
        this.validate(q);

        if (this.find(q) == this.find(p))
            return;

        this.parents[this.find(p)] = this.find(q);

        count--;
    }

    @Deprecated
    boolean connected(int p, int q) {
        this.validate(p);
        this.validate(q);
        return this.find(p) == this.find(q);
    }

    public static void main(String[] args) {

    }
}

WeightedQuickUnionUF

public class WeightedQuickUnionUF {
    private final int[] parents;
    private final int[] weight;
    private int count;

    public WeightedQuickUnionUF(int N) {
        this.parents = new int[N];
        this.weight = new int[N];
        this.count = N;

        for (int i = 0; i < N; i++) {
            this.parents[i] = i;
            this.weight[i] = 1;
        }
    }

    void validate(int p) {
        int len = this.parents.length;
        if (p < 0 || p > len - 1) {
            throw new IllegalArgumentException(
                    p + " is not between " + 0 + " and " + (len - 1));
        }
    }

    int find(int p) {
        this.validate(p);
        while (p != this.parents[p])
            p = parents[p];
        return p;
    }

    void union(int p, int q) {
        this.validate(p);
        this.validate(q);
        int rootP = this.find(p);
        int rootQ = this.find(q);

        if (rootP == rootQ) return;

        if (this.weight[rootP] >= this.weight[rootQ]) {
            this.parents[rootQ] = rootP;
            this.weight[rootP] += this.weight[rootQ];
        }
        else {
            this.parents[rootP] = rootQ;
            this.weight[rootQ] += this.weight[rootP];
        }
        count--;
    }

    int count(int p) {
        this.validate(p);
        return this.count;
    }


    public static void main(String[] args) {

    }
}

WeightedQuickUnionUFWithPathCompression

public class WeightedQuickUnionUFPathCompression {
    private final int[] parent;
    private final int[] weight;
    private int count;

    public WeightedQuickUnionUFPathCompression(int N) {
        this.parent = new int[N];
        this.weight = new int[N];
        this.count = N;

        for (int i = 0; i < N; i++) {
            this.parent[i] = i;
            this.weight[i] = 1;
        }
    }

    void validate(int p) {
        int len = this.parent.length;
        if (p < 0 || p > len - 1) {
            throw new IllegalArgumentException(
                    p + " is not between " + 0 + " and " + (len - 1));
        }
    }

    // recursive find
    int find(int p) {
        if (p != parent[p])
            parent[p] = this.find(this.parent[p]);
        return parent[p];
    }

    // int find(int p) {
    //     this.validate(p);
    //     int root = p;
    //
    //     // find root of id p
    //     while (root != this.parent[root])
    //         root = parent[root];
    //
    //     // find
    //     while (p != this.parent[p]) {
    //         int newP = this.parent[p];
    //         this.parent[p] = root;
    //         p = newP;
    //     }
    //     return p;
    // }

    void union(int p, int q) {
        this.validate(p);
        this.validate(q);
        int rootP = this.find(p);
        int rootQ = this.find(q);

        if (rootP == rootQ) return;

        if (this.weight[rootP] < this.weight[rootQ]) {
            this.parent[rootP] = rootQ;
            this.weight[rootQ] += this.weight[rootP];
        }
        else {
            this.parent[rootQ] = rootP;
            this.weight[rootP] += this.weight[rootQ];
        }
        count--;
    }

    int count(int p) {
        this.validate(p);
        return this.count;
    }

    public static void main(String[] args) {

    }
}