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