@@ -0,0 +1,2477 @@
+package me.alivecode.algs4;%0A%0Aimport edu.princeton.cs.algs4.StdIn;%0Aimport edu.princeton.cs.algs4.StdOut;%0A%0A%0Apublic class WeightedQuickUnionUF %7B%0A    private int%5B%5D parent;%0A    private int%5B%5D size;%0A    private int count;%0A%0A    public WeightedQuickUnionUF(int n) %7B%0A        parent = new int%5Bn%5D;%0A        size = new int%5Bn%5D;%0A        for (int i = 0; i %3C n; i++) %7B%0A            parent%5Bi%5D = i;%0A            size%5Bi%5D = 1;%0A        %7D%0A        count = n;%0A    %7D%0A%0A    public int count() %7B%0A        return count;%0A    %7D%0A%0A    public void validate(int p) %7B%0A        int n = parent.length;%0A        if (p %3C 0 %7C%7C p %3E= n) %7B%0A            throw new IndexOutOfBoundsException(%22Index %22 + p + %22 is not between 0 and %22 + (n - 1) + %22.%22);%0A        %7D%0A    %7D%0A%0A    public int find(int p) %7B%0A        validate(p);%0A        while (p != parent%5Bp%5D) %7B%0A            parent%5Bp%5D = parent%5Bparent%5Bp%5D%5D;%0A            p = parent%5Bp%5D;%0A        %7D%0A        return p;%0A    %7D%0A%0A    public boolean connected(int p, int q) %7B%0A        return find(p) == find(q);%0A    %7D%0A%0A    public void union(int p, int q) %7B%0A        int pRoot = find(p);%0A        int qRoot = find(q);%0A        if (pRoot == qRoot) %7B%0A            return;%0A        %7D%0A        if (size%5BpRoot%5D %3C= size%5BqRoot%5D) %7B%0A            parent%5BpRoot%5D = qRoot;%0A            size%5BqRoot%5D += size%5BpRoot%5D;%0A        %7D else %7B%0A            parent%5BqRoot%5D = pRoot;%0A            size%5BpRoot%5D += size%5BqRoot%5D;%0A        %7D%0A        count--;%0A    %7D%0A%0A    // Print the structure for testing reason.%0A    void printStructure()%7B%0A        int n = parent.length;%0A        StdOut.printf(%22%25-8s%22, %22site:%22);%0A        for(int i = 0; i %3C n; i++) %7B%0A            StdOut.printf(%22%254d%22, i);%0A        %7D%0A        StdOut.printf(%22%5Cn%25-8s%22, %22linked:%22);%0A        for(int i = 0; i %3C n; i++) %7B%0A            StdOut.printf(%22%254d%22, parent%5Bi%5D);%0A        %7D%0A        StdOut.printf(%22%5Cn%25-8s%22, %22size:%22);%0A        for(int i = 0; i %3C n; i++) %7B%0A            StdOut.printf(%22%254d%22, size%5Bi%5D);%0A        %7D%0A        StdOut.println();%0A    %7D%0A%0A    public static void main(String%5B%5D args) %7B%0A        int n = StdIn.readInt();%0A        WeightedQuickUnionUF uf = new WeightedQuickUnionUF(n);%0A        uf.printStructure();%0A        while (!StdIn.isEmpty()) %7B%0A            int p = StdIn.readInt();%0A            int q = StdIn.readInt();%0A            if (uf.connected(p, q)) %7B%0A                continue;%0A            %7D%0A            uf.union(p, q);%0A            uf.printStructure();%0A            StdOut.println(p + %22 + %22 + q);%0A        %7D%0A        uf.printStructure();%0A        StdOut.println(uf.count() + %22 components.%22);%0A    %7D%0A%7D%0A

Add weighted quick union union find.