算法
(并查集、建立双射关系)
对于第三种操作的询问,我们不需要知道每个球分别在哪个箱子里,只需知道一堆球里的代表球即可。可以分两个阶段找出“每个箱子里哪个球是代表球”以及“每个代表球在哪个箱子里”。
注意,前两种操作会破坏双射关系。
C++ 代码
#include <bits/stdc++.h>
#if __has_include(<atcoder/all>)
#include <atcoder/all>
using namespace atcoder;
#endif
#define rep(i, n) for (int i = 0; i < (n); ++i)
using namespace std;
int main() {
int n, q;
cin >> n >> q;
int mx = n+q+1;
dsu uf(mx);
vector<int> g2box(mx, -1);
vector<int> box2g(n+1, -1);
auto add = [&](int ball, int box) {
if (ball == -1) return;
int g = uf.leader(ball);
g2box[g] = box;
box2g[box] = g;
};
auto del = [&](int box) {
int g = box2g[box];
if (g == -1) return g;
g2box[g] = -1;
box2g[box] = -1;
return g;
};
for (int i = 1; i <= n; ++i) add(i, i);
int id = n+1;
rep(qi, q) {
int type, x;
cin >> type >> x;
if (type == 1) {
int y;
cin >> y;
int gx = del(x);
int gy = del(y);
if (gx == -1) swap(gx, gy);
if (gy != -1) uf.merge(gx, gy);
add(gx, x);
}
if (type == 2) {
int gx = del(x);
int gy = id; id++;
if (gx == -1) swap(gx, gy);
if (gy != -1) uf.merge(gx, gy);
add(gx, x);
}
if (type == 3) {
int g = uf.leader(x);
cout << g2box[g] << '\n';
}
}
return 0;
}