并查集学习笔记

普通并查集

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

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

实现方法：

首先，创建一个数组，用来储存第 $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;
}

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

以后再讲