src/graph/topo_sort/lib.hpp
| Line | Branch | Exec | Source |
|---|---|---|---|
| 1 | #pragma once | ||
| 2 | |||
| 3 | #include "../ds/graph_c/lib.hpp" | ||
| 4 | |||
| 5 | namespace tifa_libs { | ||
| 6 | |||
| 7 | //! return empty vector if @g is not DAG | ||
| 8 | template <graph_c G> | ||
| 9 | 69 | CEXP vecu topo_sort(G CR g) NE { | |
| 10 | 69 | cu32 n = g.vsize(); | |
| 11 | 207 | vecb vis(n), _(n); | |
| 12 | 69 | vecu ans; | |
| 13 | 101745 | auto dfs = [&](auto&& dfs, u32 i) NE -> bool { | |
| 14 |
2/2✓ Branch 2 taken 31 times.
✓ Branch 3 taken 101645 times.
|
101676 | if (_[i]) return false; |
| 15 |
2/2✓ Branch 2 taken 21136 times.
✓ Branch 3 taken 80509 times.
|
101645 | if (!vis[i]) { |
| 16 |
2/2✓ Branch 8 taken 96126 times.
✓ Branch 9 taken 20863 times.
|
116989 | for (_[i] = true; auto to : g[i]) |
| 17 |
2/2✓ Branch 2 taken 273 times.
✓ Branch 3 taken 95853 times.
|
96126 | if (!dfs(dfs, (u32)to)) return false; |
| 18 | 20863 | vis[i] = true, ans.push_back(i), _[i] = false; | |
| 19 | } | ||
| 20 | 101372 | return true; | |
| 21 | }; | ||
| 22 |
2/2✓ Branch 0 taken 20828 times.
✓ Branch 1 taken 38 times.
|
20866 | flt_ (u32, i, 0, n) |
| 23 |
6/6✓ Branch 2 taken 5550 times.
✓ Branch 3 taken 15278 times.
✓ Branch 5 taken 31 times.
✓ Branch 6 taken 5519 times.
✓ Branch 7 taken 31 times.
✓ Branch 8 taken 20797 times.
|
20828 | if (!vis[i] && !dfs(dfs, i)) return {}; |
| 24 | 38 | reverse(ans); | |
| 25 | 38 | return ans; | |
| 26 | 69 | } | |
| 27 | |||
| 28 | } // namespace tifa_libs | ||
| 29 |