Output the whole partition as node equivalence classes: if there are K
parts and N nodes, node_equivalence_classes[i] will contain the part index
(a number in 0..K-1) of node #i. Parts will be sorted by their first node
(i.e. node 0 will always be in part 0; then the next node that isn't in
part 0 will be in part 1, and so on).
Returns the number K of classes.
FOR DEBUGGING OR SPECIAL "CONST" ACCESS ONLY:
Find the root of the union-find tree with leaf 'node', i.e. its
representative node, but don't use path compression.
The amortized complexity can be as bad as log(N), as opposed to the
version using path compression.
Get the representative of "node" (a node in the same equivalence class,
which will also be returned for any other "node" in the same class).
The complexity if the same as MergePartsOf().
Complexity: amortized O(Ackermann⁻¹(N)) -- which is essentially O(1) --
where N is the number of nodes.
Return value: If this merge caused a representative node (of either node1
or node2) to stop being a representative (because only one can remain);
this method returns that removed representative. Otherwise it returns -1.
Details: a smaller part will always be merged onto a larger one.
Upons ties, the smaller representative becomes the overall representative.
Advanced usage: sets 'node' to be in its original singleton. All nodes
who may point to 'node' as a parent will remain in an inconsistent state.
This can be used to reinitialize a MergingPartition that has been sparsely
modified in O(|modifications|).
CRASHES IF USED INCORRECTLY.
[[["Easy to understand","easyToUnderstand","thumb-up"],["Solved my problem","solvedMyProblem","thumb-up"],["Other","otherUp","thumb-up"]],[["Missing the information I need","missingTheInformationINeed","thumb-down"],["Too complicated / too many steps","tooComplicatedTooManySteps","thumb-down"],["Out of date","outOfDate","thumb-down"],["Samples / code issue","samplesCodeIssue","thumb-down"],["Other","otherDown","thumb-down"]],["Last updated 2024-08-06 UTC."],[[["\u003cp\u003eThe \u003ccode\u003eMergingPartition\u003c/code\u003e class in C++ implements a partition (disjoint-set) data structure using the union-find algorithm.\u003c/p\u003e\n"],["\u003cp\u003eIt efficiently supports merging parts (sets) and finding the representative element of a part.\u003c/p\u003e\n"],["\u003cp\u003eInitially, each node belongs to its own individual part, and \u003ccode\u003eMergePartsOf\u003c/code\u003e can be used to combine them.\u003c/p\u003e\n"],["\u003cp\u003eThe class provides methods to access and manipulate the partition, such as retrieving the root of a node's set or obtaining equivalence classes.\u003c/p\u003e\n"],["\u003cp\u003e\u003ccode\u003eMergingPartition\u003c/code\u003e offers functionalities for debugging, resetting, and specialized operations like keeping only one node per part.\u003c/p\u003e\n"]]],["The `MergingPartition` class uses the union-find algorithm for incremental merging. Key actions include merging parts using `MergePartsOf`, which efficiently unites node equivalence classes, returning a removed representative if any. `GetRootAndCompressPath` finds a node's representative with path compression. `FillEquivalenceClasses` outputs the partition structure as equivalence classes. `DebugString` dumps all component with sorted nodes and parts. `KeepOnlyOneNodePerPart` prunes to one node per part. The class allows to `Reset` and `ResetNode` , initialize, get the number of nodes `NumNodes` and `NumNodesInSamePartAs`.\n"],null,["# MergingPartition\n\nC++ Reference: class MergingPartition\n=====================================\n\n\nNote: This documentation is automatically generated.\nPartition class that supports incremental merging, using the union-find algorithm (see \u003chttp://en.wikipedia.org/wiki/Disjoint-set_data_structure\u003e).\n\n| Method ||\n|----------------------------------------------------------------------------------------------------------------------|---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------|\n| [`DebugString`](https://github.com/google/or-tools/blob/v9.4/ortools/algorithms/dynamic_partition.h#L244) | Return type: `std::string ` Dump all components, with nodes sorted within each part and parts sorted lexicographically. Eg. \"0 1 3 4 \\| 2 5 \\| 6 7 8\". |\n| [`FillEquivalenceClasses`](https://github.com/google/or-tools/blob/v9.4/ortools/algorithms/dynamic_partition.h#L240) | Return type: `int ` Arguments: `std::vector\u003cint\u003e* node_equivalence_classes` Output the whole partition as node equivalence classes: if there are K parts and N nodes, node_equivalence_classes\\[i\\] will contain the part index (a number in 0..K-1) of node #i. Parts will be sorted by their first node (i.e. node 0 will always be in part 0; then the next node that isn't in part 0 will be in part 1, and so on). Returns the number K of classes. |\n| [`GetRoot`](https://github.com/google/or-tools/blob/v9.4/ortools/algorithms/dynamic_partition.h#L262) | Return type: `int ` Arguments: `int node` FOR DEBUGGING OR SPECIAL \"CONST\" ACCESS ONLY: Find the root of the union-find tree with leaf 'node', i.e. its representative node, but don't use path compression. The amortized complexity can be as bad as log(N), as opposed to the version using path compression. |\n| [`GetRootAndCompressPath`](https://github.com/google/or-tools/blob/v9.4/ortools/algorithms/dynamic_partition.h#L228) | Return type: `int ` Arguments: `int node` Get the representative of \"node\" (a node in the same equivalence class, which will also be returned for any other \"node\" in the same class). The complexity if the same as MergePartsOf(). |\n| [`KeepOnlyOneNodePerPart`](https://github.com/google/or-tools/blob/v9.4/ortools/algorithms/dynamic_partition.h#L232) | Return type: `void ` Arguments: `std::vector\u003cint\u003e* nodes` Specialized reader API: prunes \"nodes\" to only keep at most one node per part: any node which is in the same part as an earlier node will be pruned. |\n| [`MergePartsOf`](https://github.com/google/or-tools/blob/v9.4/ortools/algorithms/dynamic_partition.h#L223) | Return type: `int ` Arguments: `int node1, int node2` Complexity: amortized O(Ackermann⁻¹(N)) -- which is essentially O(1) -- where N is the number of nodes. Return value: If this merge caused a representative node (of either node1 or node2) to stop being a representative (because only one can remain); this method returns that removed representative. Otherwise it returns -1. Details: a smaller part will always be merged onto a larger one. Upons ties, the smaller representative becomes the overall representative. |\n| [`MergingPartition`](https://github.com/google/or-tools/blob/v9.4/ortools/algorithms/dynamic_partition.h#L208) | At first, all nodes are in their own singleton part. |\n| [`MergingPartition`](https://github.com/google/or-tools/blob/v9.4/ortools/algorithms/dynamic_partition.h#L209) | Return type: `explicit ` Arguments: `int num_nodes` \u003cbr /\u003e |\n| [`NumNodes`](https://github.com/google/or-tools/blob/v9.4/ortools/algorithms/dynamic_partition.h#L212) | Return type: `int ` \u003cbr /\u003e |\n| [`NumNodesInSamePartAs`](https://github.com/google/or-tools/blob/v9.4/ortools/algorithms/dynamic_partition.h#L253) | Return type: `int ` Arguments: `int node` \u003cbr /\u003e |\n| [`Reset`](https://github.com/google/or-tools/blob/v9.4/ortools/algorithms/dynamic_partition.h#L210) | Return type: `void ` Arguments: `int num_nodes` \u003cbr /\u003e |\n| [`ResetNode`](https://github.com/google/or-tools/blob/v9.4/ortools/algorithms/dynamic_partition.h#L251) | Return type: `void ` Arguments: `int node` Advanced usage: sets 'node' to be in its original singleton. All nodes who may point to 'node' as a parent will remain in an inconsistent state. This can be used to reinitialize a MergingPartition that has been sparsely modified in O(\\|modifications\\|). CRASHES IF USED INCORRECTLY. |"]]
