P12274 题解

lbbbbbbbb · 2026-05-07 15:28:00 · 题解

upd on 2026.5.8：更正了文章格式以符合洛谷题解规范，感谢管理大大的审核。

一道可撤销并查集的模板题。

题目要求我们实现 3 个操作：

• 两个节点之间连边。
• 删除上一次连的边。
• 查询两点之间的联通情况。

其中操作 1 和操作 3 都是普通的并查集可以实现的，故我们只用考虑如何进行删除操作。

注意到我们只会删除上一次的连边，所以可以自然地想到使用栈维护每一次删除时的信息。

于是，我们只需要在栈中记录每次合并时较下面的节点，每次删除时在树上删除该连边即可。

但是这引入了一个新的问题，我们常使用的路径压缩会改变并查集中的连边关系，直接与我们在树上删除边的操作冲突了，故我们只能使用按秩合并保证每次 O(\log n) 的复杂度。

至于维护树高还是子树大小取决于读者自身，其均能保证树高为 \log n，但笔者推荐维护子树大小。因为感觉更好写。

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 3e5 + 10;
int n, m;
int fa[MAXN], siz[MAXN];
stack<int> st;
int find(int x){
    if(fa[x] != x) return find(fa[x]);
    return fa[x];
}
void merge(int x, int y){
    int r1 = find(x), r2 = find(y);
    if(r1 == r2) return st.push(0), void();//压入 0 表示冗余边
    if(siz[r1] < siz[r2]) swap(r1, r2);
    fa[r2] = r1, siz[r1] += siz[r2], st.push(r2);
}
void del(){
    if(!st.size()) return;
    int u = st.top(); st.pop();
    if(u == 0) return;
    siz[fa[u]] -= siz[u], fa[u] = u;
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m;
    for(int i = 1; i <= n; i++) fa[i] = i, siz[i] = 1;
    for(int que = 1, opt, x, y; que <= m; que++){
        cin >> opt;
        if(opt == 1) cin >> x >> y, merge(x, y);
        else if(opt == 2) del();
        else cin >> x >> y, cout << (find(x) == find(y) ? "Yes" : "No") << '\n';
    }
    return 0;
}

一个有意思的点是，部分题解在栈中维护了多个冗余的变量，但实际上只需要维护一个变量即可。