src/graph/scc/kosaraju/lib.hpp
| Line | Branch | Exec | Source |
|---|---|---|---|
| 1 | #pragma once | ||
| 2 | |||
| 3 | #include "../../ds/alist/lib.hpp" | ||
| 4 | #include "../../make_graphr/lib.hpp" | ||
| 5 | |||
| 6 | namespace tifa_libs { | ||
| 7 | |||
| 8 | template <graph_c G> | ||
| 9 | class kosaraju { | ||
| 10 | G CR g; | ||
| 11 | G CR rev_g; | ||
| 12 | |||
| 13 | public: | ||
| 14 | G dag; | ||
| 15 | vecu scc_id; | ||
| 16 | vvecu belongs; | ||
| 17 | |||
| 18 | 36 | CEXP kosaraju(G CR g, G CR rev_g) NE : g(g), rev_g(rev_g), dag(0) { build(); } | |
| 19 | 36 | CEXP kosaraju(G CR g) NE : kosaraju(g, make_graphr(g)) {} | |
| 20 | |||
| 21 | private: | ||
| 22 | 36 | CEXP void build() NE { | |
| 23 | 36 | vecb vis(g.vsize()); | |
| 24 | 36 | vecu ord; | |
| 25 | 8864080 | auto dfs = [&, this](auto&& dfs, u32 idx) NE { | |
| 26 |
2/2✓ Branch 2 taken 4313251 times.
✓ Branch 3 taken 4550793 times.
|
8864044 | if (vis[idx]) return; |
| 27 |
2/2✓ Branch 10 taken 4313251 times.
✓ Branch 11 taken 4550793 times.
|
8864044 | for (vis[idx] = true; auto to : g[idx]) dfs(dfs, to); |
| 28 | 4550793 | ord.push_back(idx); | |
| 29 | }; | ||
| 30 | 8371570 | auto rdfs = [this](auto&& rdfs, u32 idx, u32 cnt) NE { | |
| 31 |
2/2✓ Branch 1 taken 3820741 times.
✓ Branch 2 taken 4550793 times.
|
8371534 | if (~scc_id[idx]) return; |
| 32 |
2/2✓ Branch 9 taken 4313251 times.
✓ Branch 10 taken 4550793 times.
|
8864044 | for (scc_id[idx] = cnt; auto to : rev_g[idx]) rdfs(rdfs, to, cnt); |
| 33 | }; | ||
| 34 |
2/2✓ Branch 2 taken 4550793 times.
✓ Branch 3 taken 36 times.
|
4550829 | flt_ (u32, i, 0, g.vsize()) dfs(dfs, i); |
| 35 | 36 | reverse(ord), scc_id.resize(g.vsize(), -1_u32); | |
| 36 | 36 | u32 cnt = 0; | |
| 37 |
2/2✓ Branch 5 taken 4550793 times.
✓ Branch 6 taken 36 times.
|
4550829 | for (u32 i : ord) |
| 38 |
2/2✓ Branch 1 taken 4058283 times.
✓ Branch 2 taken 492510 times.
|
4550793 | if (!~scc_id[i]) rdfs(rdfs, i, cnt++); |
| 39 | 36 | dag = G(cnt), belongs.resize(cnt); | |
| 40 |
2/2✓ Branch 1 taken 4550793 times.
✓ Branch 2 taken 36 times.
|
4550829 | flt_ (u32, i, 0, g.vsize()) |
| 41 |
2/2✓ Branch 9 taken 4313251 times.
✓ Branch 10 taken 4550793 times.
|
8864044 | for (belongs[scc_id[i]].push_back(i); auto to : g[i]) |
| 42 |
2/2✓ Branch 3 taken 3449773 times.
✓ Branch 4 taken 863478 times.
|
4313251 | if (u32 x = scc_id[i], y = scc_id[to]; x != y) dag.add_arc(x, y); |
| 43 | 36 | } | |
| 44 | }; | ||
| 45 | |||
| 46 | } // namespace tifa_libs | ||
| 47 |