the disjoint sets class an application an example of the use of the union/find data structure is the generation of mazessuch as the one shown in figure in figure the starting point is the top-left cornerand the ending point is the bottom-right corner we can view the maze as -by- rectangle of cells in which the top-left cell is connected to the bottom-right celland cells are separated from their neighboring cells via walls simple algorithm to generate the maze is to start with walls everywhere (except for the entrance and exitwe then continually choose wall randomlyand knock it down if the cells that the wall separates are not already connected to each other if we repeat this process until the starting and ending cells are connectedthen we have maze it is actually better to continue knocking down walls until every cell is reachable from every other cell (this generates more false leads in the mazewe illustrate the algorithm with -by- maze figure shows the initial configuration we use the union/find data structure to represent sets of cells that are connected to each other initiallywalls are everywhereand each cell is in its own equivalence class figure shows later stage of the algorithmafter few walls have been knocked down supposeat this stagethe wall that connects cells and is randomly targeted because and are already connected (they are in the same set)we would not remove the wallas it would simply trivialize the maze suppose that cells and are randomly targeted next by performing two find operationswe see that these are in different setsthus and are not already connected thereforewe knock down the wall that separates themas shown in figure notice that as result of this operationthe sets figure -by- maze