src/ds/dsu/basic/lib.hpp
| Line | Branch | Exec | Source |
|---|---|---|---|
| 1 | #pragma once | ||
| 2 | |||
| 3 | #include "../../../util/alias/others/lib.hpp" | ||
| 4 | |||
| 5 | namespace tifa_libs { | ||
| 6 | |||
| 7 | template <bool union_by_size = true> | ||
| 8 | class dsu_basic { | ||
| 9 | veci p; | ||
| 10 | |||
| 11 | public: | ||
| 12 | 360 | CEXPE dsu_basic(u32 sz) NE : p(sz, -1) {} | |
| 13 | |||
| 14 |
2/2✓ Branch 1 taken 33520737 times.
✓ Branch 2 taken 21963951 times.
|
55484688 | CEXP i32 find(u32 x) NE { retif_((p[x] < 0), (i32)x, p[x] = find((u32)p[x])); } |
| 15 | 20 | ND CEXP u32 size() CNE { return (u32)p.size(); } | |
| 16 | CEXP u32 size(u32 x) NE { return (u32)-p[(u32)find(x)]; } | ||
| 17 | 1156298 | CEXP bool same(u32 x, u32 y) NE { return find(x) == find(y); } | |
| 18 | 14259981 | CEXP bool merge(u32 x, u32 y) NE { | |
| 19 |
2/2✓ Branch 2 taken 5623422 times.
✓ Branch 3 taken 8636559 times.
|
14259981 | if ((x = (u32)find(x)) == (y = (u32)find(y))) return false; |
| 20 | if CEXP (union_by_size) | ||
| 21 |
2/2✓ Branch 2 taken 1844898 times.
✓ Branch 3 taken 6791661 times.
|
8636559 | if (p[x] > p[y]) swap(x, y); |
| 22 | 8636559 | p[x] += p[y], p[y] = (i32)x; | |
| 23 | 8636559 | return true; | |
| 24 | } | ||
| 25 | }; | ||
| 26 | |||
| 27 | } // namespace tifa_libs | ||
| 28 |