Java Disjoint Set Union -For the given code class, add a public method displaySubsets() that takes no arguments and prints out the contents of the id[] array from id[0] to id[n-1] (Same code, just neatly print out a one dimensional array]

-Replace each main() method with the corresponding code that I will give you below these specifications. (Just implement it in the code) -Run the test that is specified by modified main() -Draw the tree diagram that corresponds to the result of displaySubsets() (There should be 3 results from the algorithm)

* replacement main( ) for QuickFindUF.java * Given a set of n = 64 objects * Test QuickFindUF in three different ways and print the results * Test 1(a): u(0, 1), u(1, 2), u(2, 3) ... u(62, 63) * Test 1(b): u(0, 63), u(1, 63), u(2, 63) ... u(62, 63) * Test 1(c): Merge into 16 subsets each of size 4, then 4 subsets each of size 16, * then one subset of all 64 elements */ public static void main(String[] args) { int n = 64; QuickFindUF uf = new QuickFindUF(n); for ( int k = 0; k < n-1; k++ ) uf.union(k, k+1); uf.displaySubsets( ); // Test 1(a) uf = new QuickFindUF(n); // equivalent to reset, old gets garbage collected for ( int k = 0; k < n-1; k++ ) uf.union(k, n-1); uf.displaySubsets( ); // Test 1(b) uf = new QuickFindUF(n); // equivalent to reset, old gets garbage collected for ( int k = 0; k < n-1; k += 4 ) { uf.union(k, k+1); uf.union(k+2, k+3); uf.union(k, k+3); } for ( int k = 0; k < n-1; k += 16 ) { uf.union(k, k+4); uf.union(k, k+8); uf.union(k, k+12); } uf.union(0, 16); uf.union(0, 32); uf.union(0, 48); uf.displaySubsets( ); // Test 1(c) } -- ORIGINAL METHOD CODE BELOW THIS LINE --

public class QuickFindUF { private int[] id; // id[i] = component identifier of i private int count; // number of components /** * Initializes an empty union-find data structure with * {@code n} elements {@code 0} through {@code n-1}. * Initially, each element is in its own set. * * @param n the number of elements * @throws IllegalArgumentException if {@code n < 0} */ public QuickFindUF(int n) { count = n; id = new int[n]; for (int i = 0; i < n; i++) id[i] = i; } /** * Returns the number of sets. * * @return the number of sets (between {@code 1} and {@code n}) */ public int count() { return count; } /** * Returns the canonical element of the set containing element {@code p}. * * @param p an element * @return the canonical element of the set containing {@code p} * @throws IllegalArgumentException unless {@code 0 <= p < n} */ public int find(int p) { validate(p); return id[p]; } // validate that p is a valid index private void validate(int p) { int n = id.length; if (p < 0 || p >= n) { throw new IllegalArgumentException("index " + p + " is not between 0 and " + (n-1)); } } /** * Returns true if the two elements are in the same set. * * @param p one element * @param q the other element * @return {@code true} if {@code p} and {@code q} are in the same set; * {@code false} otherwise * @throws IllegalArgumentException unless * both {@code 0 <= p < n} and {@code 0 <= q < n} * @deprecated Replace with two calls to {@link #find(int)}. */ @Deprecated public boolean connected(int p, int q) { validate(p); validate(q); return id[p] == id[q]; } /** * Merges the set containing element {@code p} with the * the set containing element {@code q}. * * @param p one element * @param q the other element * @throws IllegalArgumentException unless * both {@code 0 <= p < n} and {@code 0 <= q < n} */ public void union(int p, int q) { validate(p); validate(q); int pID = id[p]; // needed for correctness int qID = id[q]; // to reduce the number of array accesses // p and q are already in the same component if (pID == qID) return; for (int i = 0; i < id.length; i++) if (id[i] == pID) id[i] = qID; count--; } /** * Reads an integer {@code n} and a sequence of pairs of integers * (between {@code 0} and {@code n-1}) from standard input, where each integer * in the pair represents some element; * if the elements are in different sets, merge the two sets * and print the pair to standard output. * * @param args the command-line arguments */ public static void main(String[] args) { int n = StdIn.readInt(); QuickFindUF uf = new QuickFindUF(n); while (!StdIn.isEmpty()) { int p = StdIn.readInt(); int q = StdIn.readInt(); if (uf.find(p) == uf.find(q)) continue; uf.union(p, q); StdOut.println(p + " " + q); } StdOut.println(uf.count() + " components"); } }