首页 > 其他分享 >可撤销并查集

可撤销并查集

时间:2024-06-22 17:58:32浏览次数:17  
标签:std return ops int siz 查集 撤销 find

给定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

相关文章

  • 苹果企业证书被撤销后,应该如何处理已安装的应用?
    如果苹果企业证书被撤销,所有使用该证书签名的应用程序将会受到影响。对于已安装的应用,以下是可能需要采取的处理措施: 1.停止分发:立即停止使用被撤销的证书分发新的应用安装包。2.通知用户:通知所有使用这些应用程序的用户,说明证书被撤销的情况,以及这将如何影响他们的应用......
  • C++U7-09-并查集
    并查集(DisjointSetUnion)是一种树型的数据结构,主要用于处理一些不相交集合(DisjointSets)的合并及查询问题。并查集能解决什么问题?在线游戏公会管理:应用场景:在一个大型多人在线游戏中,玩家可以创建或加入公会(公会相当于一个团队或群体)。随着时间的推移,公会可能会合并或解散。......
  • 并查集——朋友圈,部落问题
    7-2朋友圈分数25全屏浏览切换布局作者 DS课程组单位 浙江大学某学校有N个学生,形成M个俱乐部。每个俱乐部里的学生有着一定相似的兴趣爱好,形成一个朋友圈。一个学生可以同时属于若干个不同的俱乐部。根据“我的朋友的朋友也是我的朋友”这个推论......
  • 算法课程笔记——可撤销并查集
    算法课程笔记——可撤销并查集Gv......
  • 算法课程笔记——并查集基础
    算法课程笔记——并查集基础......
  • L2-013 红色警报(并查集)
    1.题目L2-013红色警报分数25全屏浏览切换布局作者陈越单位浙江大学战争中保持各个城市间的连通性非常重要。本题要求你编写一个报警程序,当失去一个城市导致国家被分裂为多个无法连通的区域时,就发出红色警报。注意:若该国本来就不完全连通,是分裂的k个区域,而失去一个城......
  • C130 并查集 P1197 [JSOI2008] 星球大战
    视频链接:  P1197[JSOI2008]星球大战-洛谷|计算机科学教育新生态(luogu.com.cn)//并查集#include<iostream>#include<cstdio>#include<cstring>usingnamespacestd;constintN=400005;inth[N],from[N],to[N],ne[N],idx;voidadd(intu,intv){from[......
  • C129 并查集+01背包 P1455 搭配购买
    视频链接:C129并查集+01背包P1455搭配购买_哔哩哔哩_bilibili  E08【模板】背包DP01背包_哔哩哔哩_bilibiliP1455搭配购买-洛谷|计算机科学教育新生态(luogu.com.cn)//并查集+01背包#include<iostream>#include<cstring>#include<algorithm>usingname......
  • 赛克oj 1540 开心消消乐(并查集、模拟、回溯)
    赛氪OJ-专注于算法竞赛的在线评测系统(saikr.com)题目描述近来,小明的班上风靡着一款名为“开心消消乐”的游戏,为了成为大家眼中的超人,小明开始疯狂研究这款游戏的玩法。游戏的场景是一个......
  • 7-4 并查集【模板】
    给出一个并查集,请完成合并和查询操作。输入格式:第一行包含两个整数N、M,表示共有N个元素和M个操作。接下来M行,每行包含三个整数Zi​、Xi​、Yi​。当Zi​=1时,将Xi​与Yi​所在的集合合并。当Zi​=2时,输出Xi​与Yi​是否在同一集合内,是的话输出Y;否则的话输出N。输出格式:......