src/graph/nf/hopkap/lib.hpp
| Line | Branch | Exec | Source |
|---|---|---|---|
| 1 | #pragma once | ||
| 2 | |||
| 3 | #include "../../../util/alias/others/lib.hpp" | ||
| 4 | |||
| 5 | namespace tifa_libs { | ||
| 6 | |||
| 7 | // @param l number of vertex in left side | ||
| 8 | // @param r number of vertex in right side | ||
| 9 | // @param e arc from left to right | ||
| 10 | 84 | inline vecptu hopkap(u32 l, u32 r, vecptu CR e) NE { | |
| 11 | 168 | vvecu adj(l); | |
| 12 | 168 | vecu pre(r, -1_u32), nxt(l, -1_u32); | |
| 13 |
2/2✓ Branch 9 taken 7326050 times.
✓ Branch 10 taken 84 times.
|
7326134 | for (auto [u, v] : e) adj[u].push_back(v); |
| 14 | while (true) { | ||
| 15 | 7494 | vecu lev(l), ptr(l); | |
| 16 | 2498 | u32 max_lev = 0; | |
| 17 | 2498 | std::queue<u32> q; | |
| 18 |
2/2✓ Branch 0 taken 230134722 times.
✓ Branch 1 taken 2498 times.
|
230137220 | flt_ (u32, i, 0, l) |
| 19 |
2/2✓ Branch 1 taken 63193867 times.
✓ Branch 2 taken 166940855 times.
|
230134722 | if (!~nxt[i]) lev[i] = 1, q.push(i); |
| 20 |
2/2✓ Branch 1 taken 141381385 times.
✓ Branch 2 taken 84 times.
|
141381469 | while (!q.empty()) { |
| 21 | 141381385 | cu32 x = q.front(); | |
| 22 |
2/2✓ Branch 7 taken 252331950 times.
✓ Branch 8 taken 141381385 times.
|
393713335 | for (q.pop(); cu32 y : adj[x]) |
| 23 |
2/2✓ Branch 1 taken 3202 times.
✓ Branch 2 taken 252328748 times.
|
252331950 | if (cu32 z = pre[y]; !~z) max_lev = lev[x]; |
| 24 |
2/2✓ Branch 1 taken 84525555 times.
✓ Branch 2 taken 167803193 times.
|
252328748 | else if (!lev[z]) lev[z] = lev[x] + 1, q.push(z); |
| 25 |
2/2✓ Branch 0 taken 2414 times.
✓ Branch 1 taken 141378971 times.
|
141381385 | if (max_lev) break; |
| 26 | } | ||
| 27 |
2/2✓ Branch 0 taken 84 times.
✓ Branch 1 taken 2414 times.
|
2498 | if (!max_lev) break; |
| 28 |
2/2✓ Branch 0 taken 226813742 times.
✓ Branch 1 taken 2414 times.
|
226816156 | flt_ (u32, i, 0, l) |
| 29 |
2/2✓ Branch 1 taken 268370 times.
✓ Branch 2 taken 226545372 times.
|
226813742 | if (lev[i] > max_lev) lev[i] = 0; |
| 30 | 135956880 | auto f = [&](auto&& f, u32 x) NE -> bool { | |
| 31 |
2/2✓ Branch 4 taken 212896127 times.
✓ Branch 5 taken 132017454 times.
|
344913581 | for (; ptr[x] < adj[x].size(); ++ptr[x]) |
| 32 |
8/8✓ Branch 4 taken 210455489 times.
✓ Branch 5 taken 2440638 times.
✓ Branch 8 taken 73643355 times.
✓ Branch 9 taken 136812134 times.
✓ Branch 11 taken 1498788 times.
✓ Branch 12 taken 72144567 times.
✓ Branch 13 taken 3939426 times.
✓ Branch 14 taken 208956701 times.
|
212896127 | if (cu32 y = adj[x][ptr[x]], z = pre[y]; !~z || (lev[z] == lev[x] + 1 && f(f, z))) { |
| 33 | 3939426 | nxt[x] = y, pre[y] = x, ptr[x] = (u32)adj[x].size(); | |
| 34 | 3939426 | return true; | |
| 35 | } | ||
| 36 | 132017454 | return false; | |
| 37 | 2414 | }; | |
| 38 |
2/2✓ Branch 0 taken 226813742 times.
✓ Branch 1 taken 2414 times.
|
226816156 | flt_ (u32, i, 0, l) |
| 39 |
2/2✓ Branch 1 taken 62313525 times.
✓ Branch 2 taken 164500217 times.
|
226813742 | if (!~nxt[i]) f(f, i); |
| 40 |
6/6✓ Branch 1 taken 2414 times.
✓ Branch 2 taken 84 times.
✓ Branch 4 taken 2414 times.
✓ Branch 5 taken 84 times.
✓ Branch 7 taken 2414 times.
✓ Branch 8 taken 84 times.
|
5080 | } |
| 41 | 84 | vecptu ans; | |
| 42 |
2/2✓ Branch 0 taken 3320980 times.
✓ Branch 1 taken 84 times.
|
3321064 | flt_ (u32, i, 0, l) |
| 43 |
2/2✓ Branch 1 taken 2440638 times.
✓ Branch 2 taken 880342 times.
|
3320980 | if (~nxt[i]) ans.emplace_back(i, nxt[i]); |
| 44 | 84 | return ans; | |
| 45 | 84 | } | |
| 46 | |||
| 47 | } // namespace tifa_libs | ||
| 48 |