src/graph/cnt/ring3/lib.hpp
| Line | Branch | Exec | Source |
|---|---|---|---|
| 1 | #pragma once | ||
| 2 | |||
| 3 | #include "../../ds/alist/lib.hpp" | ||
| 4 | |||
| 5 | namespace tifa_libs { | ||
| 6 | namespace ringenum3_impl_ { | ||
| 7 | template <class F, graph_c G> | ||
| 8 | 17 | CEXP void run(G CR dg, F&& func) NE { | |
| 9 | 17 | cu32 n = dg.vsize(); | |
| 10 | 17 | vecb vis(n); | |
| 11 |
2/2✓ Branch 0 taken 642260 times.
✓ Branch 1 taken 17 times.
|
642277 | flt_ (u32, u, 0, n) { |
| 12 |
2/2✓ Branch 9 taken 779535 times.
✓ Branch 10 taken 642260 times.
|
1421795 | for (cu32 v : dg[u]) vis[v].flip(); |
| 13 |
2/2✓ Branch 7 taken 779535 times.
✓ Branch 8 taken 642260 times.
|
1421795 | for (cu32 v : dg[u]) |
| 14 |
2/2✓ Branch 7 taken 16310698 times.
✓ Branch 8 taken 779535 times.
|
17090233 | for (cu32 w : dg[v]) |
| 15 |
2/2✓ Branch 2 taken 15742394 times.
✓ Branch 3 taken 568304 times.
|
16310698 | if (vis[w]) func(u, v, w); |
| 16 |
2/2✓ Branch 9 taken 779535 times.
✓ Branch 10 taken 642260 times.
|
1421795 | for (cu32 v : dg[u]) vis[v].flip(); |
| 17 | } | ||
| 18 | 17 | } | |
| 19 | } // namespace ringenum3_impl_ | ||
| 20 | |||
| 21 | //! should be simple undirected graph | ||
| 22 | // func(u, v, w) forall {u,v,w} is C3 | ||
| 23 | template <class F> | ||
| 24 | 17 | CEXP void ringenum3(spnu deg, vecptu CR edges, F&& func) NE { | |
| 25 | 17 | alist dg((u32)deg.size()); | |
| 26 |
2/2✓ Branch 7 taken 779535 times.
✓ Branch 8 taken 17 times.
|
779552 | for (auto [u, v] : edges) { |
| 27 |
8/8✓ Branch 2 taken 485363 times.
✓ Branch 3 taken 294172 times.
✓ Branch 6 taken 190947 times.
✓ Branch 7 taken 294416 times.
✓ Branch 8 taken 50275 times.
✓ Branch 9 taken 140672 times.
✓ Branch 10 taken 344447 times.
✓ Branch 11 taken 435088 times.
|
779535 | if (deg[u] < deg[v] || (deg[u] == deg[v] && u > v)) swap(u, v); |
| 28 | 779535 | dg.add_arc(u, v); | |
| 29 | } | ||
| 30 | 17 | ringenum3_impl_::run(dg, std::forward<F>(func)); | |
| 31 | 17 | } | |
| 32 | //! vertex ID: 0..n-1 | ||
| 33 | //! should be simple undirected graph | ||
| 34 | // func(u, v, w) forall {u,v,w} is C3 | ||
| 35 | template <class F> | ||
| 36 | 17 | CEXP void ringenum3(u32 n, vecptu CR edges, F&& func) { | |
| 37 |
1/2✓ Branch 1 taken 17 times.
✗ Branch 2 not taken.
|
17 | vecu deg(n); |
| 38 |
2/2✓ Branch 9 taken 779535 times.
✓ Branch 10 taken 17 times.
|
779552 | for (auto [u, v] : edges) ++deg[u], ++deg[v]; |
| 39 | 17 | ringenum3(deg, edges, std::forward<F>(func)); | |
| 40 | 17 | } | |
| 41 | CEXP u64 ringcnt3(u32 n, vecptu CR edges) NE { | ||
| 42 | u64 ans = 0; | ||
| 43 | ringenum3(n, edges, [&](u32, u32, u32) NE { ++ans; }); | ||
| 44 | return ans; | ||
| 45 | } | ||
| 46 | |||
| 47 | } // namespace tifa_libs | ||
| 48 |