wilderfield
All Classes Files Functions
union_find.hpp
Go to the documentation of this file.
1 // Copyright (c) [2024] [Bryan Wilder Field Lozano]
2 // Licensed under the MIT License. See LICENSE file in the project root for full
3 // license information.
4 
11 #ifndef INCLUDE_WILDERFIELD_UNION_FIND_HPP_
12 #define INCLUDE_WILDERFIELD_UNION_FIND_HPP_
13 
14 #include <algorithm>
15 #include <cstdlib>
16 #include <unordered_map>
17 
18 namespace wilderfield {
19 
27 template <typename T>
28 class UnionFind {
29  protected:
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;
34 
35  public:
41  void InsertNode(T u) {
42  if (!parent_of_.count(u)) {
43  parent_of_[u] = u;
44  rank_of_[u] = 1;
45  ++num_cc_;
46  }
47  }
48 
55  void Union(T u, T v) {
56  // Both nodes should exist
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) {
61  --num_cc_;
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]);
66  } else {
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]);
70  }
71  }
72  }
73  }
74 
81  T Find(T u) {
82  while (parent_of_[u] != u) {
83  parent_of_[u] =
84  parent_of_[parent_of_[u]]; // Path compression with grandparent
85  u = parent_of_[u];
86  }
87  return u;
88  }
89 
95  std::size_t GetMaxRank() const {
96  return max_rank_;
97  }
103  std::size_t GetNumComponents() const {
104  return num_cc_;
105  }
106 };
107 
108 } // namespace wilderfield
109 
110 #endif // INCLUDE_WILDERFIELD_UNION_FIND_HPP_
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