001// Exercise 1.5.7 (Solution published at http://algs4.cs.princeton.edu/)
002package algs15;
003import java.util.Arrays;
004import stdlib.*;
005/* **************************************************************************
006 *  Compilation:  javac QuickUnionUF.java
007 *  Execution:  java QuickUnionUF < input.txt
008 *  Dependencies: StdIn.java StdOut.java
009 *
010 *  Quick-union algorithm.
011 *
012 *  % java QuickUnionUF < largeUF.txt
013 *  QuickUnionUF # components: 6 [8332.928000] // More than 2 hours
014 *
015 ****************************************************************************/
016
017public class QuickUnionUF implements UF {
018        private int[] id;    // id[i] = parent of i
019        private int count;   // number of components
020
021        // instantiate N isolated components 0 through N-1
022        public QuickUnionUF(int N) {
023                id = new int[N];
024                count = N;
025                for (int i = 0; i < N; i++) {
026                        id[i] = i;
027                }
028        }
029
030        // return number of connected components
031        public int count() {
032                return count;
033        }
034
035        // are elements p and q in the same component?
036        public boolean connected(int p, int q) {
037                return find(p) == find(q);
038        }
039
040        // return root of component corresponding to element p
041        public int find(int p) {
042                int root = p;
043                while (root != id[root])
044                        root = id[root];
045                return root;
046        }
047
048        // merge components containing p and q
049        public void union(int p, int q) {
050                int pid = find(p); // loser
051                int qid = find(q); // champion
052                if (pid == qid) return;
053                id[pid] = qid;
054
055                count--;
056        }
057
058        public String toString() { return Arrays.toString (id); }
059        public void toGraphviz() { GraphvizBuilder.ufToFile (id); }
060
061        public static void main(String[] args) {
062                boolean print = true;
063                StdIn.fromFile ("data/tinyUF.txt"); 
064                //StdIn.fromFile ("data/tinyUFTall2.txt"); 
065                StdIn.fromFile ("data/mediumUF.txt"); print = false;
066                //StdIn.fromFile ("data/largeUF.txt"); print = false;
067
068                int N = StdIn.readInt();
069                QuickUnionUF uf = new QuickUnionUF(N);
070                if (print) { StdOut.println("   : " + uf); uf.toGraphviz(); }
071
072                // read in a sequence of pairs of integers (each in the range 0 to N-1),
073                // calling find() for each pair: If the members of the pair are not already
074                // call union() and print the pair.
075                Stopwatch sw = new Stopwatch ();
076                while (!StdIn.isEmpty()) {
077                        int p = StdIn.readInt();
078                        int q = StdIn.readInt();
079                        if (uf.connected(p, q)) continue;
080                        uf.union(p, q);
081                        if (print) { StdOut.println(p + " " + q + ": " + uf); uf.toGraphviz(); }
082                }
083                StdOut.format("QuickUnionUF # components: %d [%f]\n", uf.count(), sw.elapsedTime ());
084        }
085}