001package algs15; 002import java.util.Arrays; 003import stdlib.*; 004/* ************************************************************************** 005 * Compilation: javac WeightedUF.java 006 * Execution: java UF < input.txt 007 * Dependencies: StdIn.java StdOut.java 008 * Data files: http://algs4.cs.princeton.edu/15uf/tinytxt 009 * http://algs4.cs.princeton.edu/15uf/mediumtxt 010 * http://algs4.cs.princeton.edu/15uf/largetxt 011 * 012 * Weighted quick-union (without path compression). 013 * 014 * % java UF < tinyUF.txt 015 * 4 3 016 * 3 8 017 * 6 5 018 * 9 4 019 * 2 1 020 * 5 0 021 * 7 2 022 * 6 1 023 * # components: 2 024 * 025 * % java UF < largeUF.txt 026 * UF # components: 6 [4.372000] 027 * 028 ****************************************************************************/ 029 030 031/** 032 * The {@code UF} class represents a union-find data data structure. 033 * It supports the <em>union</em> and <em>find</em> 034 * operations, along with a method for determining the number of 035 * disjoint sets. 036 * <p> 037 * This implementation uses weighted quick union. 038 * Creating a data structure with N objects takes linear time. 039 * Afterwards, all operations are logarithmic worst-case time. 040 * <p> 041 * For additional documentation, see <a href="http://algs4.cs.princeton.edu/15uf">Section 1.5</a> of 042 * <i>Algorithms, 4th Edition</i> by Robert Sedgewick and Kevin Wayne. 043 */ 044 045public class WeightedUF implements UF { 046 private int[] id; // id[i] = parent of i 047 private int[] sz; // sz[i] = number of objects in subtree rooted at i 048 private int count; // number of components 049 050 /** 051 * Create an empty union find data structure with N isolated sets. 052 */ 053 public WeightedUF(int N) { 054 if (N < 0) throw new IllegalArgumentException(); 055 count = N; 056 id = new int[N]; 057 sz = new int[N]; 058 for (int i = 0; i < N; i++) { 059 id[i] = i; 060 sz[i] = 1; 061 } 062 } 063 064 /** 065 * Return the number of disjoint sets. 066 */ 067 public int count() { 068 return count; 069 } 070 071 /** 072 * Are objects p and q in the same set? 073 */ 074 public boolean connected(int p, int q) { 075 return find(p) == find(q); 076 } 077 078 /** 079 * Return the id of component corresponding to object p. 080 */ 081 public int find(int p) { 082 int root = p; 083 while (root != id[root]) 084 root = id[root]; 085 return root; 086 } 087 088 /** 089 * Replace sets containing p and q with their union. 090 */ 091 public void union(int p, int q) { 092 int pid = find(p); 093 int qid = find(q); 094 if (pid == qid) return; 095 096 // make smaller root point to larger one 097 // in the case of a tie, p is the champion 098 if (sz[pid] < sz[qid]) { id[pid] = qid; sz[qid] += sz[pid]; } 099 else { id[qid] = pid; sz[pid] += sz[qid]; } 100 count--; 101 } 102 103 public String toString() { return Arrays.toString (id); } 104 public void toGraphviz() { GraphvizBuilder.ufToFile (id); } 105 106 public static void main(String[] args) { 107 boolean print = true; 108 StdIn.fromFile ("data/tinyUF.txt"); 109 //StdIn.fromFile ("data/mediumUF.txt"); print = false; 110 //StdIn.fromFile ("data/largeUF.txt"); print = false; 111 112 int N = StdIn.readInt(); 113 WeightedUF uf = new WeightedUF(N); 114 if (print) { GraphvizBuilder.ufToFile (uf.id); StdOut.println(" : " + uf); } 115 116 // read in a sequence of pairs of integers (each in the range 0 to N-1), 117 // calling find() for each pair: If the members of the pair are not already 118 // call union() and print the pair. 119 Stopwatch sw = new Stopwatch (); 120 while (!StdIn.isEmpty()) { 121 int p = StdIn.readInt(); 122 int q = StdIn.readInt(); 123 if (uf.connected(p, q)) continue; 124 uf.union(p, q); 125 if (print) { StdOut.println(p + " " + q + ": " + uf); GraphvizBuilder.ufToFile (uf.id); } 126 } 127 StdOut.format("WeightedUF # components: %d [%f]\n", uf.count(), sw.elapsedTime ()); 128 } 129 130} 131