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 QuickFindUF.java
007 *  Execution:  java QuickFindUF < input.txt
008 *  Dependencies: StdIn.java StdOut.java
009 *
010 *  Quick-find algorithm.
011 *
012 *  % java QuickFindUF < largeUF.txt
013 *  QuickFindUF # components: 6 [1054.198000]  // 17 minutes
014 *
015 ****************************************************************************/
016
017public class QuickFindUF implements UF {
018        private int[] id;
019        private int count;
020
021        // instantiate N isolated components 0 through N-1
022        public QuickFindUF(int N) {
023                count = N;
024                id = new int[N];
025                for (int i = 0; i < N; i++)
026                        id[i] = i;
027        }
028
029        // return number of connected components
030        public int count() {
031                return count;
032        }
033
034
035        // are elements p and q in the same component?
036        public boolean connected(int p, int q) {
037                return id[p] == id[q];
038        }
039        
040        // Return component identifier for component containing p
041        public int find(int p) {
042                return id[p];
043        }
044
045        // merge components containing p and q
046        public void union(int p, int q) {
047                if (connected(p, q)) return;
048                int pid = id[p]; // loser
049                int qid = id[q]; // champion
050                for (int i = 0; i < id.length; i++)
051                        if (id[i] == pid) id[i] = qid;
052                count--;
053        }
054
055        public String toString() { return Arrays.toString (id); }
056        public void toGraphviz() { GraphvizBuilder.ufToFile (id); }
057
058        public static void main(String[] args) {
059                boolean print = true;
060                StdIn.fromFile ("data/tinyUF.txt"); 
061                //StdIn.fromFile ("data/mediumUF.txt"); print = false;
062                //StdIn.fromFile ("data/largeUF.txt"); print = false;
063
064                int N = StdIn.readInt();
065                QuickFindUF uf = new QuickFindUF(N);
066                if (print) { uf.toGraphviz(); StdOut.println("   : " + uf); }
067
068                // read in a sequence of pairs of integers (each in the range 0 to N-1),
069                // calling find() for each pair: If the members of the pair are not already
070                // call union() and print the pair.
071                Stopwatch sw = new Stopwatch ();
072                while (!StdIn.isEmpty()) {
073                        int p = StdIn.readInt();
074                        int q = StdIn.readInt();
075                        if (uf.connected(p, q)) continue;
076                        uf.union(p, q);
077                        if (print) { StdOut.println(p + " " + q + ": " + uf); uf.toGraphviz(); }
078                }
079                StdOut.format("QuickFindUF # components: %d [%f]\n", uf.count(), sw.elapsedTime ());
080        }
081
082}