给定n个结点,q次询问,每次询问分为三类:
- 1 x y,将x和y两个点连通,如果已经连通则不操作。
- 2,撤销上一次连通操作,如果全部撤销完了则不操作。
- 3 x y,询问x和y是否连通。
对于每个询问3,输出结果YES或NO。
提示:可销撤并查集,使用按秩合并或启发式合并,不能用路径压缩。合并时记录操作的结点信息,用于后续进行撤销。
#include <bits/stdc++.h>
using i64 = long long;
struct UndoDSU {
std::vector<int> f, siz;
std::vector<std::pair<int,int>> ops;
UndoDSU() {}
UndoDSU(int n) {
init(n);
}
void init(int n) {
f.resize(n);
std::iota(f.begin(), f.end(), 0);
siz.assign(n, 1);
ops.clear();
}
int find(int x) {
while (x != f[x]) {
x = f[f[x]];
}
return x;
}
bool join(int x, int y) {
x = find(x);
y = find(y);
if (x == y) {
return false;
}
if (siz[x] < siz[y]) {
std::swap(x, y);
}
ops.push_back({x, y});
siz[x] += siz[y];
f[y] = x;
return true;
}
bool same(int x, int y) {
return find(x) == find(y);
}
int size(int x) {
return siz[find(x)];
}
int undo() {
if (ops.empty()) {
return 0;
}
int x = ops.back().first;
int y = ops.back().second;
ops.pop_back();
siz[x] -= siz[y];
f[y] = y;
return 1;
}
};
void solve() {
int n, q;
std::cin >> n >> q;
UndoDSU dsu(n);
for (int i = 0; i < q; i++) {
int op, x, y;
std::cin >> op;
if (op == 1) {
std::cin >> x >> y;
x--, y--;
dsu.join(x, y);
} else if (op == 2) {
dsu.undo();
} else if (op == 3) {
std::cin >> x >> y;
x--, y--;
if (dsu.same(x, y)) {
std::cout << "YES\n";
} else {
std::cout << "NO\n";
}
}
}
}
int main() {
std::cin.tie(0)->sync_with_stdio(0);
int t = 1;
while (t--) solve();
return 0;
}
标签:std,return,ops,int,siz,查集,撤销,find
From: https://www.cnblogs.com/chenfy27/p/18262581