Overview: The Disjoint Set data structure will be used in the creation of a maze.

Details: Write a program to generate and display a maze The program may either be a command-line program that generates a character-based maze, or it may be a GUI program that draws the maze in a window. The user should be able to specify the number of rows and columns in the maze, at least up to 20x20. You must use the DisjSet class to implement the algorithm. The DisjSet class must be used as given without making modifications to it.

// DisjSets class // // CONSTRUCTION: with int representing initial number of sets // // ******************PUBLIC OPERATIONS********************* // void union( root1, root2 ) --> Merge two sets // int find( x ) --> Return set containing x // ******************ERRORS******************************** // No error checking is performed

/** * Disjoint set class, using union by rank and path compression. * Elements in the set are numbered starting at 0. * @author Mark Allen Weiss */ public class DisjSets { /** * Construct the disjoint sets object. * @param numElements the initial number of disjoint sets. */ public DisjSets( int numElements ) { s = new int [ numElements ]; for( int i = 0; i

/** * Union two disjoint sets using the height heuristic. * For simplicity, we assume root1 and root2 are distinct * and represent set names. * @param root1 the root of set 1. * @param root2 the root of set 2. */ public void union( int root1, int root2 ) { if( s[ root2 ]

/** * Perform a find with path compression. * Error checks omitted again for simplicity. * @param x the element being searched for. * @return the set containing x. */ public int find( int x ) { if( s[ x ]

private int [ ] s;

// Test main; all finds on same output line should be identical public static void main( String [ ] args ) { int NumElements = 128; int NumInSameSet = 16;

DisjSets ds = new DisjSets( NumElements ); int set1, set2;

for( int k = 1; k

for( int i = 0; i l DisjSets class CONSTRUCTION: with int representing initial number of sets void union root1, root2) --> Merge two sets Na error checking is performed PUBLIC OPERATIONS // int find x ) Return set containing x Disjoint set class, using union by rank and path compression. Elements in the set are numbered starting at 0. @author Mark Allen Weiss5 public class DisjSets Construct the disjoint sets object. * @param numElements the initial number of disjoint sets. public DisjSets int numElements) s = new int [ numElements ]; for( int i = 0; i s-length; it+) Union two disjoint sets using the height heuristic. *For simplicity, we assume rootl and root2 are distinct * and represent set names @param rootl the root of set 1 @param root2 the root of set 2 public void union int root, int root2) ifi s[ root2 ] s[ root! ] // root2 is deeper # Make root2 new root s[ root! ] = root2; else s[ root! ]..; s[ root2 ] = rootli I, update height if same // Make rot! new root * Perform a find with path compression Error checks omitted again for simplicity. @pararm x the element being searched for @retum the set containing x. public int find int x return else return s[ x ] = find( S(x ] ); private int [5; Test main; all finds on same output line should be identical public statc void main String [ args) int NumElements 128: int NumInsameset = 16; Disisets ds = new Disjsets( NumElements ); int setl, set2; for( int j-0; j + k NumElements; j +-2-k ) setl = dsfind( j ); set2 = ds.find{ j + k ); ds.union setl, set2 ); for( int i = 0; i