src/edh/prufer/inv.hpp
| Line | Branch | Exec | Source |
|---|---|---|---|
| 1 | #pragma once | ||
| 2 | |||
| 3 | #include "../../util/alias/others/lib.hpp" | ||
| 4 | |||
| 5 | namespace tifa_libs { | ||
| 6 | |||
| 7 | //! vertex ID starts at 1 | ||
| 8 | //! tree root = n | ||
| 9 | // prüfer code of vertex i is code[i], code[0] = 0 | ||
| 10 | 12 | CEXP vecu prufer_inv(spnu code) NE { | |
| 11 | 12 | cu32 n = u32(code.size() + 1); | |
| 12 | 12 | vecu deg(n + 1); | |
| 13 |
2/2✓ Branch 2 taken 9511086 times.
✓ Branch 3 taken 12 times.
|
9511098 | flt_ (u32, i, 1, n - 1) ++deg[code[i]]; |
| 14 | 12 | vecu fa(n); | |
| 15 |
2/2✓ Branch 0 taken 4756535 times.
✓ Branch 1 taken 12 times.
|
4756547 | for (u32 i = 1, j = 1; i < n - 1; ++i, ++j) { |
| 16 |
2/2✓ Branch 1 taken 4754562 times.
✓ Branch 2 taken 4756535 times.
|
9511097 | while (deg[j]) ++j; |
| 17 | 4756535 | fa[j] = code[i]; | |
| 18 |
10/10✓ Branch 0 taken 4754551 times.
✓ Branch 1 taken 11 times.
✓ Branch 5 taken 9511086 times.
✓ Branch 6 taken 11 times.
✓ Branch 9 taken 6011338 times.
✓ Branch 10 taken 3499748 times.
✓ Branch 12 taken 4754562 times.
✓ Branch 13 taken 1256776 times.
✓ Branch 14 taken 4754562 times.
✓ Branch 15 taken 4756535 times.
|
9511097 | while (i < n - 1 && !--deg[code[i]] && code[i] < j) fa[code[i]] = (i + 1 == n - 1 ? n : code[i + 1]), ++i; |
| 19 | } | ||
| 20 |
1/2✓ Branch 5 taken 12 times.
✗ Branch 6 not taken.
|
12 | for (auto& i : fa) |
| 21 |
1/2✓ Branch 0 taken 12 times.
✗ Branch 1 not taken.
|
12 | if (!i) { |
| 22 | 12 | i = n; | |
| 23 | 12 | break; | |
| 24 | } | ||
| 25 | 12 | return fa; | |
| 26 | 12 | } | |
| 27 | |||
| 28 | } // namespace tifa_libs | ||
| 29 |