src/graph/clique/all/lib.hpp
| Line | Branch | Exec | Source |
|---|---|---|---|
| 1 | #pragma once | ||
| 2 | |||
| 3 | #include "../../../util/alias/others/lib.hpp" | ||
| 4 | |||
| 5 | namespace tifa_libs { | ||
| 6 | |||
| 7 | // calculate $\operatorname{sum}_{c\subseteq C} \operatorname{op}_{v\in c}$, which $C$ is set of all cliques (include $\varnothing$) | ||
| 8 | // @param e_sum identity element of @sum | ||
| 9 | // @param e_op identity element of @op | ||
| 10 | template <class T, usz N, class S, class OP> | ||
| 11 | requires requires(S sum, OP op, T val1, T val2, u32 v) { | ||
| 12 | { sum(val1, val2) } -> std::same_as<T>; | ||
| 13 | { op(val1, v) } -> std::same_as<T>; | ||
| 14 | } | ||
| 15 | 23 | CEXP T clique_calc(u32 n, arr<std::bitset<N>, N> CR adj, S&& sum, OP&& op, T e_sum = T(0), T e_op = T(1)) NE { | |
| 16 | using B = std::bitset<N>; | ||
| 17 | 23 | B _{}; | |
| 18 | 23 | T ans = e_sum; | |
| 19 | 93243 | auto h = [&](auto&& h, u32 now, T t) NE -> void { | |
| 20 | 46610 | ans = sum(ans, t); | |
| 21 |
2/2✓ Branch 0 taken 108070 times.
✓ Branch 1 taken 46610 times.
|
154680 | flt_ (u32, v, now + 1, n) { |
| 22 |
2/2✓ Branch 4 taken 61483 times.
✓ Branch 5 taken 46587 times.
|
108070 | if ((_ & adj[v]).count() != _.count()) continue; |
| 23 | 46587 | _[v] = 1, h(h, v, op(t, v)), _[v] = 0; | |
| 24 | } | ||
| 25 | }; | ||
| 26 | 23 | h(h, -1_u32, e_op); | |
| 27 | 23 | return ans; | |
| 28 | } | ||
| 29 | |||
| 30 | } // namespace tifa_libs | ||
| 31 |