001// Exercise 1.5.13
002package algs15;
003import java.util.Arrays;
004import stdlib.*;
005/* **************************************************************************
006 *  Compilation:  javac WeightedQuickUnionPathCompressionUF.java
007 *  Execution:  java WeightedQuickUnionPathCompressionUF < input.txt
008 *  Dependencies: StdIn.java StdOut.java
009 *
010 *  Weighted quick-union with path compression.
011 *
012 *  % java WeightedQuickUnionPathCompressionUF < largeUF.txt
013 *  WeightedQuickUnionPathCompressionUF # components: 6 [4.375000]
014 *
015 ****************************************************************************/
016
017public class XWeightedCompressionUF implements UF {
018        private final int[] id;    // id[i] = parent of i
019        private final int[] sz;    // sz[i] = number of objects in subtree rooted at i
020        private int count;   // number of components
021
022        // Create an empty union find data structure with N isolated sets.
023        public XWeightedCompressionUF(int N) {
024                count = N;
025                id = new int[N];
026                sz = new int[N];
027                for (int i = 0; i < N; i++) {
028                        id[i] = i;
029                        sz[i] = 1;
030                }
031        }
032
033        // Return the number of disjoint sets.
034        public int count() {
035                return count;
036        }
037
038
039        // Are objects p and q in the same set?
040        public boolean connected(int p, int q) {
041                return find(p) == find(q);
042        }
043        
044        // Return component identifier for component containing p
045        public int find(int p) {
046                int root = p;
047                while (root != id[root])
048                        root = id[root];
049                while (id[p] != root) {
050                        int newp = id[p];
051                        id[p] = root;
052                        if (TestUF.SHOW_COMPRESSION_STEPS) { StdOut.format("%2d %2d> %2d%s\n", p, root, this.count(), this); toGraphviz(); }
053                        p = newp;
054                }
055                return root;
056        }
057
058        // Replace sets containing p and q with their union.
059        public void union(int p, int q) {
060                int pid = find(p);
061                int qid = find(q);
062                if (pid == qid) return;
063
064                // make smaller root point to larger one
065                // in the case of a tie, p is the champion
066                if   (sz[pid] < sz[qid]) { id[pid] = qid; sz[qid] += sz[pid]; }
067                else                     { id[qid] = pid; sz[pid] += sz[qid]; }
068                count--;
069        }
070
071        public String toString() { return Arrays.toString (id); }
072        public void toGraphviz() { GraphvizBuilder.ufToFile (id); }
073
074        public static void main(String[] args) {
075                boolean print = true;
076                StdIn.fromFile ("data/tinyUF.txt"); 
077                //StdIn.fromFile ("data/mediumUF.txt"); print = false;
078                //StdIn.fromFile ("data/largeUF.txt"); print = false;
079
080                int N = StdIn.readInt();
081                XWeightedCompressionUF uf = new XWeightedCompressionUF(N);
082                if (print) { uf.toGraphviz(); StdOut.println("   : " + uf); }
083
084                // read in a sequence of pairs of integers (each in the range 0 to N-1),
085                // calling find() for each pair: If the members of the pair are not already
086                // call union() and print the pair.
087                Stopwatch sw = new Stopwatch ();
088                while (!StdIn.isEmpty()) {
089                        int p = StdIn.readInt();
090                        int q = StdIn.readInt();
091                        if (uf.connected(p, q)) continue;
092                        uf.union(p, q);
093                        if (print) { StdOut.println(p + " " + q + ": " + uf); uf.toGraphviz(); }
094                }
095                StdOut.format("XWeightedCompressionUF # components: %d [%f]", uf.count(), sw.elapsedTime ());
096        }
097
098}
099