| 50 | |
| 51 | template <typename T> |
| 52 | void UnionFind<T>::Merge(UnionFind* other) { |
| 53 | UnionFind<T>* a = FindRoot(); |
| 54 | UnionFind<T>* b = other->FindRoot(); |
| 55 | if (a == b) return; |
| 56 | if (a->rank_ > b->rank_) { |
| 57 | b->parent_ = a; |
| 58 | a->size_ += b->size_; |
| 59 | return; |
| 60 | } |
| 61 | |
| 62 | a->parent_ = b; |
| 63 | if (a->rank_ == b->rank_) { |
| 64 | b->rank_++; |
| 65 | } |
| 66 | b->value_ = a->value_; |
| 67 | b->size_ += a->size_; |
| 68 | } |
| 69 | |
| 70 | template <typename T> |
| 71 | UnionFind<T>* UnionFind<T>::FindRoot() { |