src/graph/scc/e_tcc/lib.hpp
| Line | Branch | Exec | Source |
|---|---|---|---|
| 1 | #pragma once | ||
| 2 | |||
| 3 | #include "../../../ds/dsu/basic/lib.hpp" | ||
| 4 | #include "../../../ds/dsu/delineation/lib.hpp" | ||
| 5 | #include "../../ds/alist/lib.hpp" | ||
| 6 | |||
| 7 | namespace tifa_libs { | ||
| 8 | |||
| 9 | struct e_tcc { | ||
| 10 | vecu dfn, low, post, path, deg; | ||
| 11 | dsu_basic<> dsu; | ||
| 12 | vvecu belongs; | ||
| 13 | |||
| 14 | //! g should be undirected | ||
| 15 | template <class Et, class... Info> | ||
| 16 | 180 | CEXP e_tcc(alist<Et, Info...> CR g) NE : dfn(g.vsize(), -1_u32), low(g.vsize()), post(g.vsize()), path(g.vsize(), -1_u32), deg(g.vsize()), dsu(g.vsize()) { | |
| 17 | 20 | cu32 n = g.vsize(); | |
| 18 | 20 | u32 tot = -1_u32; | |
| 19 | 2299022 | const auto dfs = [&](auto&& f, u32 u, u32 t = -1_u32) -> void { | |
| 20 | 1149501 | u32 pc{}; | |
| 21 |
2/2✓ Branch 9 taken 3075652 times.
✓ Branch 10 taken 1149501 times.
|
4225153 | for (dfn[u] = low[u] = ++tot; u32 v : g[u]) { |
| 22 |
8/8✓ Branch 0 taken 3075628 times.
✓ Branch 1 taken 24 times.
✓ Branch 2 taken 1013551 times.
✓ Branch 3 taken 2062077 times.
✓ Branch 4 taken 1012052 times.
✓ Branch 5 taken 1499 times.
✓ Branch 6 taken 1012076 times.
✓ Branch 7 taken 2063576 times.
|
3075652 | if (v == u || (v == t && !pc++)) continue; |
| 23 |
2/2✓ Branch 1 taken 1051524 times.
✓ Branch 2 taken 1012052 times.
|
2063576 | if (~dfn[v]) { |
| 24 |
2/2✓ Branch 2 taken 525762 times.
✓ Branch 3 taken 525762 times.
|
1051524 | if (dfn[v] < dfn[u]) { |
| 25 | 525762 | ++deg[u], low[u] = std::min(low[u], dfn[v]); | |
| 26 | 525762 | continue; | |
| 27 | } | ||
| 28 | 525762 | --deg[u]; | |
| 29 |
8/8✓ Branch 1 taken 366588 times.
✓ Branch 2 taken 416881 times.
✓ Branch 5 taken 306442 times.
✓ Branch 6 taken 60146 times.
✓ Branch 9 taken 257707 times.
✓ Branch 10 taken 48735 times.
✓ Branch 11 taken 257707 times.
✓ Branch 12 taken 525762 times.
|
783469 | for (auto& p = path[u]; ~p && dfn[p] <= dfn[v] && dfn[v] <= post[p]; p = path[p]) |
| 30 | 257707 | dsu.merge(u, p), deg[u] += deg[p]; | |
| 31 | 525762 | continue; | |
| 32 | 525762 | } | |
| 33 |
7/8✓ Branch 1 taken 1012052 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 731285 times.
✓ Branch 5 taken 280767 times.
✓ Branch 7 taken 536063 times.
✓ Branch 8 taken 195222 times.
✓ Branch 9 taken 536063 times.
✓ Branch 10 taken 475989 times.
|
1012052 | if (f(f, v, u); !~path[v] && deg[v] <= 1) { |
| 34 | 536063 | low[u] = min(low[u], low[v]), deg[u] += deg[v]; | |
| 35 | 536063 | continue; | |
| 36 | } | ||
| 37 |
2/2✓ Branch 1 taken 132083 times.
✓ Branch 2 taken 343906 times.
|
475989 | if (!deg[v]) v = path[v]; |
| 38 |
2/2✓ Branch 2 taken 445245 times.
✓ Branch 3 taken 30744 times.
|
475989 | if (low[u] > low[v]) low[u] = min(low[u], low[v]), swap(v, path[u]); |
| 39 |
2/2✓ Branch 4 taken 86199 times.
✓ Branch 5 taken 475989 times.
|
562188 | for (; ~v; v = path[v]) dsu.merge(u, v), deg[u] += deg[v]; |
| 40 | } | ||
| 41 | 1149501 | post[u] = tot; | |
| 42 | }; | ||
| 43 |
2/2✓ Branch 0 taken 1149501 times.
✓ Branch 1 taken 20 times.
|
1149521 | flt_ (u32, u, 0, n) |
| 44 |
2/2✓ Branch 1 taken 137449 times.
✓ Branch 2 taken 1012052 times.
|
1149501 | if (!~dfn[u]) dfs(dfs, u); |
| 45 | 20 | belongs = dsu_delineation(dsu); | |
| 46 | 20 | } | |
| 47 | }; | ||
| 48 | |||
| 49 | } // namespace tifa_libs | ||
| 50 |