21 #ifndef FST_UNION_FIND_H_ 22 #define FST_UNION_FIND_H_ 35 UnionFind(T max, T fail) : parent_(max, fail), rank_(max), fail_(fail) {}
40 if (item >= parent_.size() || item == fail_ || parent_[item] == fail_) {
44 while (root != parent_[root]) {
47 while (item != parent_[item]) {
48 T parent = parent_[item];
61 if (item >= parent_.size()) {
63 const auto nitem = item > 0 ? 2 * item : 2;
64 parent_.resize(nitem, fail_);
74 for (T item = 0; item < max; ++item) parent_[item] = item;
78 const T &
Parent(
const T &x)
const {
return parent_[x]; }
84 if (rank_[x] > rank_[y]) {
88 if (rank_[x] == rank_[y]) {
98 std::vector<T> parent_;
99 std::vector<int> rank_;
105 #endif // FST_UNION_FIND_H_
const T & Parent(const T &x) const