Question

Can some body please clearly describe how a disjoint–set ADT can be used to solve equidivisions problem and as well as how dfs can be used to solve it?

Answer 1

A disjoint set data structure keeps track of elements partitioned into a number of disjoint subsets. In computer science, two sets are said to be disjoint if they have no element in common.The disjoint sets problem is a problem of efficiently mantaining a collection C of disjoint subsets of some set S, That is , each element of the set S is contained in a singleton subset. With this as the initial state of the collections we wish to efficiently support two of the following operations in the disjoint set problem:The configuration of the disjoint sets is that of an equivalence relation with each collection representing an equivalence class . In this problem we would be assigning a representative for each equivalence class / disjoint subset . Depth first search (DFS) algorithm starts with the initial node of the graph G, and then goes to deeper and deeper until we find the goal node or the node which has no children. The algorithm, then backtracks from the dead end towards the most recent node that is yet to be completely unexplored.