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