素集合データ構造 (DataStructure/disjoint_set.cpp)
- category: DataStructure
-
View this file on GitHub
- Last commit date: 2020-04-28 18:27:31+09:00
Verified with
Code
#ifndef H_disjoint_set
#define H_disjoint_set
/**
* @brief 素集合データ構造
* @author えびちゃん
*/
#include <cstddef>
#include <cstdint>
#include <utility>
#include <vector>
class disjoint_set {
public:
using size_type = size_t;
private:
mutable std::vector<intmax_t> M_c;
public:
disjoint_set() = default;
explicit disjoint_set(size_type n): M_c(n, -1) {}
void reset() { M_c.assign(M_c.size(), -1); }
size_type representative(size_type v) const {
if (M_c[v] < 0) return v;
return (M_c[v] = representative(M_c[v]));
}
bool unite(size_type u, size_type v) {
u = representative(u);
v = representative(v);
if (u == v) return false;
if (-M_c[u] > -M_c[v]) std::swap(u, v);
M_c[v] += M_c[u];
M_c[u] = v;
return true;
}
bool equivalent(size_type u, size_type v) const {
return (representative(u) == representative(v));
}
size_type size() const noexcept { return M_c.size(); }
size_type count(size_type v) const {
return -M_c[representative(v)];
}
};
#endif /* !defined(H_disjoint_set) */
#line 1 "DataStructure/disjoint_set.cpp"
/**
* @brief 素集合データ構造
* @author えびちゃん
*/
#include <cstddef>
#include <cstdint>
#include <utility>
#include <vector>
class disjoint_set {
public:
using size_type = size_t;
private:
mutable std::vector<intmax_t> M_c;
public:
disjoint_set() = default;
explicit disjoint_set(size_type n): M_c(n, -1) {}
void reset() { M_c.assign(M_c.size(), -1); }
size_type representative(size_type v) const {
if (M_c[v] < 0) return v;
return (M_c[v] = representative(M_c[v]));
}
bool unite(size_type u, size_type v) {
u = representative(u);
v = representative(v);
if (u == v) return false;
if (-M_c[u] > -M_c[v]) std::swap(u, v);
M_c[v] += M_c[u];
M_c[u] = v;
return true;
}
bool equivalent(size_type u, size_type v) const {
return (representative(u) == representative(v));
}
size_type size() const noexcept { return M_c.size(); }
size_type count(size_type v) const {
return -M_c[representative(v)];
}
};