Partition refinement
In the design of algorithms, partition refinement is a technique for representing a partition of a set as a data structure that allows the partition to be refined by splitting its sets into a larger number of smaller sets. In that sense it is dual to the union-find data structure, which also maintains a partition into disjoint sets but in which the operations merge pairs of sets together.
Partition refinement forms a key component of several efficient algorithms on graphs and finite automata, including DFA minimization, the Coffman–Graham algorithm for parallel scheduling, and lexicographic breadth-first search of graphs.
A partition refinement algorithm maintains a family of disjoint sets Si. At the start of the algorithm, this family contains a single set of all the elements in the data structure. At each step of the algorithm, a set X is presented to the algorithm, and each set Si in the family that contains members of X is split into two sets, the intersection Si ∩ X and the difference Si \ X.
Such an algorithm may be implemented efficiently by maintaining data structures representing the following information:array, ordered by the sets they belong to, and sets may be represented by start and end indices into this array.
To perform a refinement operation, the algorithm loops through the elements of the given set X. For each such element x, it finds the set Si that contains x, and checks whether a second set for Si ∩ X has already been started. If not, it creates the second set and add Si to a list L of the sets that are split by the operation. Then, regardless of whether a new set was formed, the algorithm removes x from Si and adds it to Si ∩ X. In the representation in which all elements are stored in a single array, moving x from one set to another may be performed by swapping x with the final element of Si and then decrementing the end index of Si and the start index of the new set. Finally, after all elements of X have been processed in this way, the algorithm loops through L, separating each current set Si from the second set that has been split from it, and reports both of these sets as being newly formed by the refinement operation.
...
Wikipedia