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}