首页 > 其他分享 >数据结构——并查集 学习笔记

数据结构——并查集 学习笔记

时间：2024-07-09 22:08:28浏览次数：10  
标签：dsu return int 查集 笔记 fa unite getfa 数据结构

数据结构——并查集 学习笔记

并查集是一种用于管理元素所属集合的数据结构，实现为一个森林。

并查集中，每棵树表示一个集合，树中的节点表示对应集合中的元素。

其思想是，把集合属性绑定到根节点上，避免多余的处理，因此一般难以分离。

普通并查集

并查集支持两种操作：

  • 合并（Union）：合并两个元素所属集合（合并对应的树）；
  • 查询（Find）：查询某个元素所属集合（查询对应的树的根节点）。
struct dsu {
    vector<int> fa;
    dsu(int siz): fa(siz) { iota(fa.begin(), fa.end(), 0); }
    int getfa(int x) { return x == fa[x] ? x : getfa(fa[x]); }
    void unite(int x, int y) { fa[getfa(x)] = getfa(y); }
};

路径压缩

一个不通用的优化，我们把任意一个非根节点直接合并到它的根上。

struct dsu {
    vector<int> fa;
    dsu(int siz): fa(siz) { iota(fa.begin(), fa.end(), 0); }
    int getfa(int x) { return x == fa[x] ? x : fa[x] = getfa(fa[x]); }
    void unite(int x, int y) { fa[getfa(x)] = getfa(y); }
};

非常好写，但是对于可撤销等就无法压缩了。

启发式合并和按秩合并

合并时，选择哪棵树的根节点作为新树的根节点会很大程度上影响复杂度。

一般来说，我们可以将节点较少或深度较小的树连到另一棵，以免发生退化。

  • 其中，按照节点个数合并，称为启发式合并（维护树的大小）。
  • 而按照深度（称为秩）合并的，称为按秩合并（维护树的高度）。

一定程度上，启发式合并会被卡，但是按秩合并会比较难写。

代码略。

复杂度分析

如果只使用路径压缩或启发式合并，时间复杂度是单次 \(\mathcal O(\log n)\) 的。

如果同时使用，时间复杂度是单次 \(\mathcal O(\alpha(n))\) 的，可以近似看成单次 \(\mathcal O(1)\)。

扩展域并查集

扩展域并查集用于维护两类及以上集合的连通性。

具体的，我们一般开多倍空间，用 \(x,x+n,\dots\) 表示同一个物体的不同属性。

这种用多个域表示同一元素不同属性的，也称为种类并查集。

P1892 [BOI2003] 团伙

经典例题：P1892 [BOI2003] 团伙。

我们用 \(F[1,N]\) 表示朋友域，用 \(F[N+1,2N]\) 表示敌人域。

  • 若 \(x,y\) 是朋友，那么直接连接 \(\langle x,y\rangle\)，表示他俩是朋友；
  • 若 \(x,y\) 是敌人，那么连接 \(\langle x,y+N\rangle,\langle x+N,y\rangle\)，表示敌人的敌人是朋友。

例如 \(A\to B\to C\)，其中只有 \(B\) 是敌人域的，那么 \(A\) 敌人 \(B\) 的敌人 \(C\) 就是 \(A\) 的朋友。

点击查看代码 
#include <bits/stdc++.h>

using namespace std;

struct dsu {
    vector<int> fa;
    dsu(int siz): fa(siz) { iota(fa.begin(), fa.end(), 0); }
    int getfa(int x) { return x == fa[x] ? x : fa[x] = getfa(fa[x]); }
    void unite(int x, int y) { fa[getfa(x)] = getfa(y); }
};

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);
    int n, m;
    cin >> n >> m;
    dsu a(2 * n + 1);
    while (m--) {
        char op[3];
        int x, y;
        cin >> op >> x >> y;
        if (op[0] == 'F') a.unite(x, y);
        else a.unite(x + n, y), a.unite(y + n, x);
    }
    int res = 0;
    for (int i = 1; i <= n; ++i)
        res += a.fa[i] == i;
    cout << res << endl;
    return 0;
}

P2024 [NOI2001] 食物链

一个比经典例题还经典的例题：P2024 [NOI2001] 食物链。

我们另，

  • \(x\) 表示本体；
  • \(x+n\) 表示 \(x\) 的事物集合；
  • \(x+2n\) 表示 \(x\) 的天敌集合。
点击查看代码 
#include <bits/stdc++.h>

using namespace std;

#define endl "\n"

struct dsu {
    vector<int> fa;
    dsu() = default;
    dsu(int siz): fa(siz) { iota(fa.begin(), fa.end(), 0); }
    int getfa(int x) { return x == fa[x] ? x : fa[x] = getfa(fa[x]); }
    void unite(int x, int y) { fa[getfa(x)] = getfa(y); }
};

int n, k;

dsu a;

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);
    cin >> n >> k;
    a = dsu(3 * n + 1);
    // x:         >_<
    // x + n:     x's food
    // x + 2 * n: x's enemy
    auto uni = [] (int x, int y) -> bool {
        if (a.getfa(x) == a.getfa(y + n)) return false;
        if (a.getfa(x) == a.getfa(y + 2 * n)) return false;
        a.unite(x, y), a.unite(x + n, y + n), a.unite(x + 2 * n, y + 2 * n);
        return true;
    };
    auto eat = [] (int x, int y) -> bool {
        if (a.getfa(x) == a.getfa(y)) return false;
        if (a.getfa(x) == a.getfa(y + n)) return false;
        a.unite(x + n, y), a.unite(x, y + 2 * n), a.unite(x + 2 * n, y + n);
        return true;
    };
    int ans = 0;
    while (k--) {
        int op, x, y;
        cin >> op >> x >> y;
        if (x > n || y > n) ++ans;
        else if (op == 1) ans += !uni(x, y);
        else if (op == 2) ans += !eat(x, y);
    }
    cout << ans << endl;
    return 0;
}

我们可以总结出来，

  • 扩展域并查集，一定要搞清楚要开几个维度，连边必须讨论清楚，尽量多连；
  • 一般来说，通常有几个维度就至少要连几条边。

带权并查集

带权并查集，也称为边带权并查集。

我们在并查集的边上定义某种权值，从而解决更多的问题。

而因为路径压缩的存在，我们一般要定义这种权值在路径压缩时产生的运算。

P2024 [NOI2001] 食物链

你说得对，这道题也可以用带权并查集来做。

在边权上维护模 3 意义下的加法群，从根开始计算两个点的深度差

\[d=d(x)-d(y) \]

  • \(d\equiv0\pmod3\)，则 \(x,y\) 属于同类；
  • \(d\equiv1\pmod3\)，则 \(x\) 吃 \(y\)，\(x\) 是 \(y\) 的天敌；
  • \(d\equiv0\pmod3\)，则 \(y\) 吃 \(x\)，\(y\) 是 \(x\) 的天敌；

当我们在路径压缩的时候，注意我们记录的 \(d(x)\) 表示的是 \(x\) 到其父节点的距离，

  • 那么，我们已经跑完了一个节点的祖先，其父节点一定是直接接在根上面的。
  • 于是，我们另一个节点的新的距离直接为其父节点到祖先（父节点的父节点）的距离加上其到其父节点的距离即可。
int getfa(int x) {
    if (x == fa[x]) return x;
    int t = getfa(fa[x]);
    d[x] = d[x] + d[fa[x]];
    return fa[x] = t;
}

合并的时候，默认把 \(x\) 分支接在 \(y\) 的祖先上，分类讨论即可，

  • 因为已经路径压缩了，因此 \(x,y\) 的父节点一定就是根节点。
  • 若 \(x,y\) 是同类，则合并其父节点时要保证其深度相同，于是取 \(d(y)-d(x)\)；
  • 若 \(x\) 吃 \(y\)，那么要使 \(x\) 比 \(y\) 高一级，取 \(d(y)-d(x)+1\)。

这两个数的本质就是，我们再向上合并的时候要加上 \(d(x)\)，则可以抵消。

点击查看代码 
#include <bits/stdc++.h>

using namespace std;

#define endl "\n"

struct dsu {
    vector<int> fa, d;
    dsu() = default;
    dsu(int siz): fa(siz), d(siz) { iota(fa.begin(), fa.end(), 0); }
    int getfa(int x) {
        if (x == fa[x]) return x;
        int t = getfa(fa[x]);
        d[x] = d[x] + d[fa[x]];
        return fa[x] = t;
    }
};

int n, k;

dsu a;

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);
    cin >> n >> k;
    a = dsu(n + 1);
    auto uni = [] (int x, int y) -> bool {
        int px = a.getfa(x);
        int py = a.getfa(y);
        if (px != py) {
            a.fa[px] = py;
            a.d[px] = a.d[y] - a.d[x];
            return true;
        }
        return ((a.d[x] - a.d[y]) % 3 + 3) % 3 == 0;
    };
    auto eat = [] (int x, int y) -> bool {
        int px = a.getfa(x);
        int py = a.getfa(y);
        if (px != py) {
            a.fa[px] = py;
            a.d[px] = a.d[y] - a.d[x] + 1;
            return true;
        }
        return ((a.d[x] - a.d[y]) % 3 + 3) % 3 == 1;
    };
    int ans = 0;
    while (k--) {
        int op, x, y;
        cin >> op >> x >> y;
        if (x > n || y > n) ++ans;
        else if (op == 1) ans += !uni(x, y);
        else if (op == 2) ans += !eat(x, y);
    }
    cout << ans << endl;
    return 0;
}

P1196 [NOI2002] 银河英雄传说

同时维护边权和集合大小。

注意到如果把一个队列 \(A\) 接到 \(B\)，相当于 \(A\) 加上边权为集合 \(B\) 的大小，直接接到 \(B\) 的根上。

我们根据这个，直接维护即可。

点击查看代码 
#include <bits/stdc++.h>

using namespace std;

struct dsu {
    vector<int> fa, siz, d;
    dsu() = default;
    dsu(int n): fa(n), siz(n, 1), d(n) { iota(fa.begin(), fa.end(), 0); }
    int getfa(int x) {
        if (x == fa[x]) return x;
        int t = getfa(fa[x]);
        d[x] = d[x] + d[fa[x]];
        return fa[x] = t;
    }
    // merge x to y
    void unite(int x, int y) {
        x = getfa(x), y = getfa(y);
        fa[x] = y, d[x] = siz[y];
        siz[y] += siz[x];
    }
};

dsu a(30005);

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);
    int T; cin >> T;
    while (T--) {
        char op[3];
        int x, y;
        cin >> op >> x >> y;
        if (op[0] == 'M') a.unite(x, y);
        else {
            if (a.getfa(x) != a.getfa(y)) cout << "-1" << endl;
            else cout << abs(a.d[x] - a.d[y]) - 1 << endl;
        }
    }
    return 0;
}

经典例题分析

P1955 [NOI2015] 程序自动分析

有若干组条件，可能为 \(a_i=a_j\) 或 \(a_i\neq a_j\)，请判断是否合法。

注意到我们先把等于的 unite 起来，然后再检查不等于的是否合法即可。

离散化可以使用 umap 复杂度低（如果是 CF 建议使用 map）（。

P1197 [JSOI2008] 星球大战

每次打掉图中的几个点，询问连通块数量。

注意到并查集可以快速查询连通块数量，但是很难支持删除操作。

但是并查集可以很快的完成加入，因此我们正难则反。

  1. 先把被打掉的点一口气打掉，处理连通块；
  2. 从后往前加入被打掉的点，记录连通块数量。

注意一些细节，实现是很简单的。

点击查看代码 
#include <bits/stdc++.h>

using namespace std;

#define endl "\n"

constexpr int N = 4e5 + 10;

int n, m;

int hack[N];
bool hacked[N];

vector<int> g[N];

int fa[N], tot;

int getfa(int x) {
    if (x == fa[x]) return x;
    return fa[x] = getfa(fa[x]);
}

void unite(int x, int y) {
    x = getfa(x), y = getfa(y);
    if (x != y) fa[x] = y, --tot;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);
    cin >> n >> m;
    tot = n;
    for (int i = 1; i <= n; ++i)
        fa[i] = i;
    for (int i = 0; i < m; ++i) {
        int u, v;
        cin >> u >> v;
        ++u, ++v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    int k;
    cin >> k;
    for (int i = 0; i < k; ++i) {
        cin >> hack[i];
        hacked[++hack[i]] = true;
    }
    for (int i = 1; i <= n; ++i) {
        if (hacked[i]) continue;
        if (!g[i].empty())
        for (int j : g[i]) {
            if (hacked[j]) continue;
            unite(i, j);
        }
    }
    vector<int> ans(k + 1);
    ans[k] = tot - k;
    for (int i = k - 1; ~i; --i) {
        int x = hack[i];
        hacked[x] = 0;
        if (!g[x].empty())
        for (int y : g[x]) {
            if (hacked[y]) continue;
            unite(x, y);
        }
        ans[i] = tot - i;
    }
    for (int i : ans)
        cout << i << endl;
    return 0;
}

AT_abc238_e [ABC238E] Range Sums

题目描述：有一个长为 \(N\) 的序列，判断根据 \(Q\) 个区间 \([l_i,r_i]\) 的和，是否能确定整个序列的元素和。

我们注意到，当确定了 \([l,r]\) 的和，我们其实已经确定了 \(S_r-S_{l-1}\) 的值。

那么，我们经过若干次传递，如果能从 \(S_N\) 转移到 \(S_0\)，那么就是可行的。

这就是一个并查集板子了，代码略。

P5937 [CEOI1999] Parity Game

类似的，我们设 \(S\) 为二进制序列的前缀和。

那么，我们的 \([l,r]\) 信息，也就是知道了 \(S_r-S_{l-1}\) 的奇偶性。

我们用扩展域并查集，

  • 若为偶数，连边 \(\langle l,r\rangle,\langle l+n,r+n\rangle\)，表示这两个奇偶性相同。
  • 若为奇数，连边 \(\langle l+n,r\rangle,\langle l,r+n\rangle\)，表示奇偶性不同。

如果连边的时候发现，同一组如果出现了另一组的边，那么失效。

提前离散化一下即可。

点击查看代码 
#include <bits/stdc++.h>

using namespace std;

#define endl "\n"

struct query_t {
    int l, r;
    bool iseven;
};

struct dsu_t {
    vector<int> fa;
    dsu_t(int n): fa(n) { iota(fa.begin(), fa.end(), 0); }
    int getfa(int x) { return x == fa[x] ? x : fa[x] = getfa(fa[x]); }
    void unite(int l, int r) { fa[getfa(l)] = getfa(r); }
} dsu(1e4 + 10);

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);
    int n, m;
    cin >> n >> m;
    vector<int> s(m * 2);
    vector<query_t> a(m);
    for (int i = 0; i < m; ++i) {
        int l, r; string op;
        cin >> l >> r >> op;
        --l;
        s[i] = l, s[i + m] = r;
        a[i] = (query_t){l, r, op == "even"};
    }
    sort(s.begin(), s.end());
    s.erase(unique(s.begin(), s.end()), s.end());
    n = s.size();
    #define getid(x) (lower_bound(s.begin(), s.end(), x) - s.begin() + 1)
    for (int i = 0; i < m; ++i) {
        int op = a[i].iseven;
        int l = getid(a[i].l), r = getid(a[i].r);
        // cout << "MERGE " << l << " " << r << " " << op << " WA " << n << endl;
        if (op == 1) {
            if (dsu.getfa(l) == dsu.getfa(r + n) || dsu.getfa(l + n) == dsu.getfa(r))
                cout << i << endl, exit(0);
            dsu.unite(l, r), dsu.unite(l + n, r + n);
        } else {
            if (dsu.getfa(l) == dsu.getfa(r) || dsu.getfa(l + n) == dsu.getfa(r + n))
                cout << i << endl, exit(0);
            dsu.unite(l, r + n), dsu.unite(l + n, r);
        }
    }
    cout << m << endl;
    return 0;
}

标签：dsu,return,int,查集,笔记,fa,unite,getfa,数据结构
From： https://www.cnblogs.com/RainPPR/p/18288876

相关文章

  • 第五篇、Python列表：多功能的数据结构
    在Python编程中，列表是一种极其重要且灵活的数据结构。本文将深入探讨Python中的列表，包括列表的定义、遍历方法和常见操作。一、列表的定义列表是Python中最常用的数据类型之一，它是一个可变的、有序的元素集合。列表的特点包括：可以存储不同类型的数据元素之间用逗号分隔使用......
  • 「学习笔记」数位DP
    虽然叫DP，但是基本所有数位DP题我们都可以用好打好想好理解的记忆化搜索来做。记搜模板有一个大致的记忆化搜索模板，AKALL数位DPintdfs(intlen,boollead,boollimit,...){ if(!len)return1;//len=0,即所有位都搜完 if(~f[len][lead][limit]...)returnf[l......
  • 下降幂学习笔记
    下降幂学习笔记还原精灵还我笔记——来自打完笔记但关电脑前没有保存的某人的呐喊。定义下降幂就是形如\(n^{\underline{m}}\)的式子，表示\[n^{\underline{m}}=\prod_{i=n-m+1}^{n}=\frac{n!}{(n-m)!}\]同理声明一个上升幂\(n^{\overline{m}}\)，表示\[n^{\overline{m}}=\pr......
  • 数据结构之折半查找
     折半查找的算法思想：折半查找又称二分查找，它仅仅适用于有序的顺表。折半查找的基本思想：首先将给定值key与表中中间位置的元素（mid的指向元素）比较。mid=low+high/2（向下取整）若key与中间元素相等，则查找成功，返回该元素的存储位置，即mid；若key与中间元素不相等，则所需查找的元素只......
  • 根本听不懂的也看不懂的上课笔记
    https://qoj.ac/problem/8008不难发现，随机到某些位置，之后最短路先O（nm）预处理出能到的点，考虑最小的随机位置CF741C考虑二分图染色，对于每一对情侣，相互连边，相邻的2i和2i-1也连边，都代表颜色不同，CF1656G限制是只有一个环，先随便造一个回文排列现有一个排列p如果i，j处在同一......
  • 信创学习笔记(二),信创之CPU芯片架构思维导图
    创作不易只因热爱!!热衷分享，一起成长!“你的鼓励就是我努力付出的动力”各架构,操作系统,指令,代表生产商,服务器使用产品主要供应商......
  • 信创学习笔记(一),信创内容思维导图
    创作不易只因热爱!!热衷分享，一起成长!“你的鼓励就是我努力付出的动力”用一张图归纳学习信创内容信创内容思维导图......
  • 并查集
    <2024.7.9>基本概念：主要用于解决一些元素分组的问题。它管理一系列不相交的集合，并支持两种操作：合并（Union）：把两个不相交的集合合并为一个集合。查询（Find）：查询两个元素是否在同一个集合中使用步骤：初始化，假设每个人指向自己根据每个人的意向确定边的连接选出一个集合的代......
  • Dotnet算法与数据结构：Hashset, List对比
    哈希集A是存储唯一元素的集合。它通过在内部使用哈希表来实现这一点，该哈希表为基本操作（如添加、删除和包含）提供恒定时间平均复杂度（O（1））。此外，不允许重复元素，使其成为唯一性至关重要的场景的理想选择。另一方面，表示按顺序存储元素的动态数组。它允许重复元素并提供对元素的索引......
  • 快速傅里叶变换复习笔记
    .real()成员函数FFT的本质是快速计算多项式的点值表示对负实数的四舍五入需要-0.5编写函数接收数组地址时，注意不能破坏原数组FFT有较为严重的精度问题，double甚至难以准确计算两个\(10^9\)级别的整数相乘的结果，即使采用longdouble也时常无法得到准确的答案，这或许也是模板题中......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99