// @file disjoint_set.h // @author Denis Felipe // @version 0.1 // // @brief // Disjoint-set data structure, also known as Union-Find or Merge-Find. // // @example // #include // #include "disjoint_set.h" // // int main(int argc, char** argv) // { // data_structure::DisjointSet disjoint_set(10); // Generate three disjoint sets of a single element. // // // Merge a series of sets. Print true if two different sets were merged. // std::cout << "Merge: " << disjoint_set.merge(0, 2) << std::endl; // std::cout << "Merge: " << disjoint_set.merge(1, 4) << std::endl; // std::cout << "Merge: " << disjoint_set.merge(1, 5) << std::endl; // std::cout << "Merge: " << disjoint_set.merge(4, 5) << std::endl; // std::cout << "Merge: " << disjoint_set.merge(4, 8) << std::endl; // std::cout << "Merge: " << disjoint_set.merge(4, 8) << std::endl; // // // Print the representative of each element. // for (size_t i = 0; i < 10; ++i) // {std::cout << i << ": " << disjoint_set.find(i) << std::endl;} // // return 0; // } // function main // // @section LICENSE // Copyright (c) 2017, Denis Felipe // All rights reserved. // // Redistribution and use in source and binary forms, with or without // modification, are permitted provided that the following conditions are met: // // 1. Redistributions of source code must retain the above copyright notice, this // list of conditions and the following disclaimer. // 2. Redistributions in binary form must reproduce the above copyright notice, // this list of conditions and the following disclaimer in the documentation // and/or other materials provided with the distribution. // // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND // ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED // WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE // DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR // ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES // (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; // LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND // ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS // SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. // // The views and conclusions contained in the software and documentation are those // of the authors and should not be interpreted as representing official policies, // either expressed or implied, of the FreeBSD Project. // #define guard to prevent multiple inclusion. #ifndef DISJOINT_SET_H #define DISJOINT_SET_H #include #include #include namespace data_structure { // @class DisjointSet // @brief // Disjoint-set data structure, also known as Union-Find or Merge-Find. class DisjointSet { public: // Constructor // @param size_t $size // Number of elements. DisjointSet(const size_t& size) : parent_(size) {std::iota(parent_.begin(), parent_.end(), 0);} // ctor // Destructor ~DisjointSet() {;} // dtor // @brief // Merge two sets in one. Apply the splicing method to compact the tree. // // @param int $x // Element of the first set. // @param int $y // Element of the second set. // // @return bool // True if the sets containing elements $x and $y are different, false otherwise. const bool merge(const int& x, const int& y) { int element_x = x; int element_y = y; int z = 0; while (parent_[element_x] != parent_[element_y]) { if (parent_[element_x] > parent_[element_y]) {std::swap(element_x, element_y);} z = parent_[element_x]; parent_[element_x] = parent_[element_y]; if (element_x == z) {return true;} element_x = z; } return false; } // function merge // @brief // Find the representative of a set. Apply the splitting method to compact the tree. // // @param int $x // Element of the set. // // @return int // Representative of the set containing element $x. const int find(const int& x) { int element_x = x; int parent_x = parent_[element_x]; while (parent_x != parent_[parent_x]) { parent_[element_x] = parent_[parent_x]; element_x = parent_x; parent_x = parent_[element_x]; } return parent_x; } // function find private: // @brief // Representative of each element. std::vector parent_; }; // class DisjointSet } // namespace data_structure #endif // DISJOINT_SET_H

disjoin_set.h