38 if (num_nodes == old_num_nodes) {
44 parent_.resize(num_nodes);
45 std::iota(parent_.begin() + old_num_nodes, parent_.end(), old_num_nodes);
47 component_size_.resize(num_nodes, 1);
49 rank_.resize(num_nodes);
51 num_components_ += num_nodes - old_num_nodes;
59 int root = parent_[node];
60 while (parent_[root] != root) {
65 while (node != root) {
66 const int prev_parent = parent_[node];
75 if (num_nodes != num_nodes_at_last_get_roots_call_) {
79 const int previous_num_roots = roots_.size();
80 roots_.resize(previous_num_roots + num_nodes -
81 num_nodes_at_last_get_roots_call_);
82 std::iota(roots_.begin() + previous_num_roots, roots_.end(),
83 num_nodes_at_last_get_roots_call_);
90 &roots_, [&](
const int node) {
return node !=
FindRoot(node); });
92 num_nodes_at_last_get_roots_call_ = num_nodes;
98 const int min_num_nodes =
std::max(node1, node2) + 1;
108 if (root1 == root2) {
115 const int component_size = component_size_[root1] + component_size_[root2];
120 if (rank_[root1] > rank_[root2]) {
121 parent_[root2] = root1;
122 component_size_[root1] = component_size;
124 parent_[root1] = root2;
125 component_size_[root2] = component_size;
127 if (rank_[root1] == rank_[root2]) {
145 return component_size_[
FindRoot(node)];
150 int current_component = 0;
152 int& root_component = component_ids[
FindRoot(node)];
153 if (root_component < 0) {
155 root_component = current_component;
158 component_ids[node] = root_component;
160 return component_ids;