题目描述
难度分:$1777$
输入$n(2 \leq n \leq 3 \times 10^5)$表示有$n$个盒子,编号从$1$到$n$。
每个盒子都放了一个小球,其中编号为$i$的盒子放了编号为$i$的小球。
然后输入$q(1 \leq q \leq 3 \times 10^5)$和$q$个操作,格式如下:
-
$1$ $x$ $y$:把编号为$y$的盒子中的小球全部放入编号为$x$的盒子中。保证$x \neq y$。
-
$2$ $x$:设所有盒子中一共有$k$个小球,现在把一个新的编号为$k+1$的小球放入编号为$x$的盒子中。
-
$3$ $x$:输出编号为$x$的小球所在盒子的编号。保证$x$一定在某个盒子中。
输入样例
5 10
3 5
1 1 4
2 1
2 4
3 7
1 3 1
3 4
1 1 4
3 7
3 6
输出样例
5
4
3
1
3
算法
并查集
这个题很容易想到用并查集来做,对于并查集的$father$数组$p$,赋予$p[i]$的含义为“小球$i$在箱子$p[i]$中”。但是对于操作$1$,将$y$箱子中的小球倒入$x$箱子后,$y$箱子还可以放入新的小球,这会导致后来放入$y$的小球如果仅靠并查集来查询的话,会直接定位到$x$箱子,而这样是不对的。
可以这样来处理,将$y$中的小球倒入$x$之后,如果再来新的小球要放进$y$,就开一个新的箱子$z$ $(z \gt n)$来放,并记录$z$对应的原始箱子。
复杂度分析
时间复杂度
初始化并查集的时间复杂度为$O(n+q)$,接下来的$q$次操作,除了第$3$种操作,其他两种是$O(1)$的,第$3$种是并查集的查询操作,时间复杂度是$log$级别。因此,算法整体的时间复杂度为$O(n+q+qlogn)$。
空间复杂度
空间消耗的瓶颈由并查集决定,额外空间复杂度为$O(n+q)$。
C++ 代码
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 600010;
int p[N], newBox[N], originBox[N], n, q;
int find(int x) {
return p[x] == x? x: p[x] = find(p[x]);
}
int main() {
scanf("%d%d", &n, &q);
for(int i = 1; i < N; i++) {
p[i] = i;
newBox[i] = i;
originBox[i] = i;
}
int k = n, z = n + q;
for(int i = 1; i <= q; i++) {
int t, x, y;
scanf("%d%d", &t, &x);
if(t == 1) {
scanf("%d", &y);
p[newBox[y]] = newBox[x];
newBox[y] = z;
originBox[z] = y;
z--;
}else if(t == 2) {
p[++k] = newBox[x];
}else {
printf("%d\n", originBox[find(x)]);
}
}
return 0;
}