F - Colored Ball
2huk
·
·
题解
F - Colored Ball
Description
有 n 个集合 S_1, S_2, \dots, S_n，最开始第 i 个集合内有且仅有一个元素 c_i。接下来需要进行 q 次操作，第 i 次操作如下：
- 将集合 S_{a_i} 中的元素全部移动到集合 S_{b_i} 中。
每次操作后，你需要求出集合 S_{b_i} 中的元素种类数量。
## Solution
合并集合，自然的想到启发式合并。
但这并不是简单的合并集合，而是将某个集合中的所有元素全部搬到另一个集合中，再把这个集合清空。
可以这样实现这件事情：仍然按照启发式合并的思路，将总数较少的集合搬到总数较多的集合中（注意这里没有区分 $a_i, b_i$），再把另一个集合清空。然后看一下，如果刚才是把集合 $b_i$ 中的元素搬到了集合 $a_i$ 里，那么就代表我们移错了。解决措施直接又快捷：将两个集合交换即可。因为交换 STL 容器是 $\Theta (1)$ 的。
总时间复杂度 $\Theta (n \log n)$，这也是启发式合并的复杂度。
## Code
<https://atcoder.jp/contests/abc329/submissions/47731747>
at_abc329_f