aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorXiaoxu Guo <shimo11370@proton.me>2024-06-06 23:20:26 +0800
committerXiaoxu Guo <shimo11370@proton.me>2024-06-06 23:20:26 +0800
commit8f7ef6bae03fca6698d9cd2eb330f01a6cc893b7 (patch)
treeee93dc2e682df768f8f176498dec4726094594d1
parentaa4179aaf33d6927bcc72b1c096bb5924668e5ad (diff)
downloadshoka-8f7ef6bae03fca6698d9cd2eb330f01a6cc893b7.tar.gz
shoka-8f7ef6bae03fca6698d9cd2eb330f01a6cc893b7.zip
fixed
-rw-r--r--eulerian_tour.h38
-rw-r--r--primality_test.h5
-rw-r--r--reroot_dp.h2
3 files changed, 23 insertions, 22 deletions
diff --git a/eulerian_tour.h b/eulerian_tour.h
index 7256adb..8b60cfe 100644
--- a/eulerian_tour.h
+++ b/eulerian_tour.h
@@ -1,23 +1,7 @@
#include <utility>
#include <vector>
-struct EulerianTour : public std::vector<int> {
- explicit EulerianTour(int n_, int s,
- const std::vector<std::pair<int, int>> &edges_)
- : n{n_}, m(edges_.size()), head(n, -1), next(m << 1),
- used(m), edges{edges_} {
- for (int i = 0; i < m << 1; ++i) {
- auto [u, v] = edges[i >> 1];
- if (i & 1) {
- std::swap(u, v);
- }
- next[i] = head[u];
- head[u] = i;
- }
- dfs(s);
- }
-
-private:
+class Eulerian {
void dfs(int u) {
while (~head[u]) {
int i = head[u];
@@ -28,11 +12,29 @@ private:
dfs(v);
}
}
- push_back(u);
+ tour.push_back(u);
}
int n, m;
std::vector<int> head, next;
std::vector<bool> used;
const std::vector<std::pair<int, int>> &edges;
+
+public:
+ explicit Eulerian(int n_, int s,
+ const std::vector<std::pair<int, int>> &edges_)
+ : n{n_}, m(edges_.size()), head(n, -1), next(m << 1), used(m),
+ edges{edges_} {
+ for (int i = 0; i < m << 1; ++i) {
+ auto [u, v] = edges[i >> 1];
+ if (i & 1) {
+ std::swap(u, v);
+ }
+ next[i] = head[u];
+ head[u] = i;
+ }
+ dfs(s);
+ }
+
+ std::vector<int> tour;
};
diff --git a/primality_test.h b/primality_test.h
index 3123317..dd0ec9f 100644
--- a/primality_test.h
+++ b/primality_test.h
@@ -1,9 +1,8 @@
#pragma once
-#include <type_traits>
+#include <concepts>
-template <typename T> static inline constexpr T is_prime(T n) {
- static_assert(std::is_integral_v<T>);
+template <std::integral T> static inline constexpr T is_prime(T n) {
if (n < 2) {
return false;
}
diff --git a/reroot_dp.h b/reroot_dp.h
index 605a5f3..07ee821 100644
--- a/reroot_dp.h
+++ b/reroot_dp.h
@@ -6,7 +6,7 @@
template <IsTreeMonoid M, IsGraph Tree>
requires std::is_same_v<GraphEdge<Tree>, std::pair<int, M>>
-class RerootDp {
+class RerootDp : public std::vector<M> {
void dfs_down(int p, int u) {
for (auto &&[v, e] : tree[u]) {
if (v != p) {