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}