diff options
Diffstat (limited to 'meowpp/dsa/DisjointSet.hpp')
-rw-r--r-- | meowpp/dsa/DisjointSet.hpp | 52 |
1 files changed, 52 insertions, 0 deletions
diff --git a/meowpp/dsa/DisjointSet.hpp b/meowpp/dsa/DisjointSet.hpp new file mode 100644 index 0000000..3b66626 --- /dev/null +++ b/meowpp/dsa/DisjointSet.hpp @@ -0,0 +1,52 @@ +#include <vector> +#include <cstdlib> + +namespace meow{ + inline size_t DisjointSet::_root(size_t now){ + if(father[now] == now) return now; + return (father[now] = _root(father[now])); + } + inline size_t DisjointSet::_merge(size_t a, size_t b){ + a = _root(a); + b = _root(b); + if(a == b) return a; + if(depth[a] > depth[b]){ + father[b] = a; + return a; + }else{ + father[a] = b; + if(depth[a] == depth[b]){ + depth[b]++; + } + return b; + } + } + // + inline DisjointSet::DisjointSet(): n(0){ } + inline DisjointSet::DisjointSet(size_t _n): n(0){ + reset(_n); + } + inline DisjointSet::DisjointSet(DisjointSet const& dsj){ + n = dsj.n; + father = dsj.father; + depth = dsj.depth; + } + // + inline size_t DisjointSet::root(size_t a) const{ + return ((DisjointSet*)this)->_root(a); + } + inline size_t DisjointSet::size() const{ return n; } + // + inline void DisjointSet::reset(size_t _n){ + n = _n; + father.resize(n); + depth .resize(n); + for(size_t i = 0; i < n; i++){ + father[i] = i; + depth [i] = 1; + } + } + inline size_t DisjointSet::merge(size_t a, size_t b){ + return _merge(a, b); + } +} |