并查集学习笔记

并查集学习笔记

普通并查集

首先,我们需要知道什么是并查集。

并查集就是一种数据结构(或算法)能够实现在一个森林中的查找和合并,其中复杂度是玄学(?)

实现方法:

首先,创建一个数组,用来储存第 $i$ 个节点的父节点。数组的第 $i$ 个元素,初始化是 $i$,在最开始每个节点的父节点就是自己,因为这个森林现在只有 $n$ 个树,每个树只有一个元素。

查找:

运用递归的方法,每次查找参数的父亲节点,直到碰到父亲节点和节点一样的。

合并:

把 x 的树并入 y 的树。

但是这样的话如果询问的次数多的话,时间复杂度就会有点高,所有我们采用路径压缩(记忆化)。

在查找的时候,我们可以把递归路途上的所有节点都更新,这样的话后几次查询时递归的次数就减少很多。

例题

P2256 一中校运会之百米跑 – 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

这道题就是一个并查集的模板(好像所有橙题模板),我们用 map 存储名字建立映射,直接套用模板。

代码:

#include <bits/stdc++.h>

using namespace std;
/*
*/
int n, m, f[100005];
map <string, int> mp;
int find(int x) {
    if (f[x] == x) return x;
    else return f[x] = find(f[x]);
}
void merge(int x, int y) {
    f[find(x)] = find(y);
    return;
}
int main() {
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= n; i ++) {
        f[i] = i;
        string s; cin >> s;
        mp[s] = i;
    }
    while (m --) {
        string y, x; cin >> x >> y;
        merge(mp[x], mp[y]);
    }
    int k; cin >> k;
    for (int i = 1; i <= k; i ++) {
        string x, y; cin >> x >> y;
        cout << (find(mp[x]) == find(mp[y]) ? "Yes." : "No.") << "\n";
    }
    return 0;
}

带权并查集

之前我们的并查集都是查询两个元素是否在一个集合里面,现在,这个并查集被加上了权值。

其实跟没权并查集一样,查找的时候只需要加一个更新权值就行了。

合并的时候就是把一个树的权值加到需要合并的树上。

题目:P1196 [NOI2002] 银河英雄传说 – 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

在这里,我们的权值就是这个战舰离队首的距离。

当一个战舰加入队伍,这个集合的大小加一,这个战舰的权值加集合的大小。

代码

#include <bits/stdc++.h>

using namespace std;
/*
*/
int f[30005], sum[30005], cnt[30005], n;
int find(int x) {
    if (f[x] == x) {
        return x;
    }
    int k = f[x];
    f[x] = find(f[x]);
    sum[x] += sum[k];
    cnt[x] = cnt[f[x]];
    return f[x];
}
void merge(int x, int y) {
    int fx = find(x); 
    int fy = find(y);
    f[fx] = fy;
    sum[fx] += cnt[fy];
    cnt[fx] += cnt[fy];
    cnt[fy] = cnt[fx];
}
int main() {
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin >> n;
    for (int i = 1; i <= 30000; i ++) f[i] = i, sum[i] = 0, cnt[i] = 1;
    while (n --) {
        char op;
        cin >> op;
        int i, j; cin >> i >> j;
        if (op == 'M') merge(i, j);
        else {
            int fx = find(i);
            int fy = find(j);
            if (fx != fy) cout << "-1\n";
            else cout << abs(sum[i] - sum[j]) - 1 << "\n";
        }
    }
    return 0;
}

还有删除和移动操作,这里就不讲了~

以后再讲

本文链接:https://ztrztr.top/archives/180
版权声明:本文 《并查集学习笔记》 为 ztrztr 原创。著作权归作者所有。
转载说明:联系作者或者评论区留言获得转载授权,并注明转载地址。
暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇