11 #ifndef INCLUDE_WILDERFIELD_UNION_FIND_HPP_
12 #define INCLUDE_WILDERFIELD_UNION_FIND_HPP_
16 #include <unordered_map>
18 namespace wilderfield {
30 std::unordered_map<T, T> parent_of_;
31 std::unordered_map<T, size_t> rank_of_;
32 std::size_t max_rank_ = 0;
33 std::size_t num_cc_ = 0;
42 if (!parent_of_.count(u)) {
57 if (parent_of_.count(u) && parent_of_.count(v)) {
58 auto repr_of_u =
Find(u);
59 auto repr_of_v =
Find(v);
60 if (repr_of_u != repr_of_v) {
62 if (rank_of_[repr_of_u] >= rank_of_[repr_of_v]) {
63 parent_of_[repr_of_v] = repr_of_u;
64 rank_of_[repr_of_u] += rank_of_[repr_of_v];
65 max_rank_ = std::max(max_rank_, rank_of_[repr_of_u]);
67 parent_of_[repr_of_u] = repr_of_v;
68 rank_of_[repr_of_v] += rank_of_[repr_of_u];
69 max_rank_ = std::max(max_rank_, rank_of_[repr_of_v]);
82 while (parent_of_[u] != u) {
84 parent_of_[parent_of_[u]];
Union Find class.
Definition: union_find.hpp:28
std::size_t GetNumComponents() const
Get the number of connected components.
Definition: union_find.hpp:103
T Find(T u)
Find the representative of a node.
Definition: union_find.hpp:81
void Union(T u, T v)
Perform union operation on two nodes.
Definition: union_find.hpp:55
void InsertNode(T u)
Insert a new node.
Definition: union_find.hpp:41
std::size_t GetMaxRank() const
Get the maximum rank in the union find structure.
Definition: union_find.hpp:95