算法竞赛进阶指南-第五章-并查集

算法竞赛进阶指南-第五章-并查集

- 12 mins
markdown components extra

感觉第四章后面的数学知识看的有些吃力(指不想动脑子),所以就先看看下面的

并查集

并查集是一种可以动态维护若干个不重叠的集合,并支持合并与查询的数据结构

两个基本操作:

​ Get,查询一个元素属于哪一个集合

​ Merge,把两个集合合并成一个大集合

集合的表示方法:”代表元”法,即为每个集合选择一个固定的元素,作为整个集合的”代表”

归属关系的表示方法:使用一个树形结构存储每个集合,树上的每个节点都是一个元素,树根是集合的代表元素

(为提高查询效率,并查集引入了路径压缩与按秩合并两种思想)

路径压缩与按秩合并

路径压缩:在每次执行Get操作的同时,把访问过的每个节点(也就是所查询元素的全部祖先)都直接指向树根

image-20230302115236262

采用路径压缩优化的并查集,每次Get操作的均摊复杂度为O(logN)

把集合的”秩”记录在”代表元素”上,在合并时都把”秩”较小的树根作为”秩”较大的树根的子节点

当”秩”定义为集合的大小时,按秩合并也称为”启发式合并”

按秩合并优化的并查集,.每次Get操作的均摊复杂度也是O(logN)

同时采用路径压缩和按秩合并优化的并查集,每次Get操作的均摊复杂度可以进一步降低到近似O(N)

image-20230302115805558

并查集能在一张无向图中维护节点之间的连通性,这是它的基本用途之一.

并查集擅长动态维护许多具有传递性的关系

程序自动分析

这道题的思路的话,就是并查集的变形,相等的就用Merge合并,不相等的就先存下来,到最后统一用Get判断,如果Get到的结果是一样的,则为NO,因为明明不等,却必须相等,否则就是YES

#include <bits/stdc++.h>
using namespace std;
int T, n, fa[200005];
map<int, int> mapp;
int beg = 0;
int get(int x)
{
    if (x == fa[x])
        return x;
    return fa[x] = get(fa[x]);
}
void merge(int x, int y)
{
    fa[get(x)] = get(y);
}
vector<int> x1, x2;
int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    cin >> T;
    while (T--)
    {
        mapp.clear();
        x1.clear();
        x2.clear();
        cin >> n;
        for (int i = 0; i <= 2 * n; i++)
        {
            fa[i] = i;
        }
        int m = 1;
        while (n--)
        {
            int a, b, e;
            cin >> a >> b >> e;
            if (!mapp[a])
                mapp[a] = m++;
            if (!mapp[b])
                mapp[b] = m++;
            if (e)
            {
                merge(mapp[a], mapp[b]);
            }
            if (!e)
            {
                x1.push_back(mapp[a]);
                x2.push_back(mapp[b]);
            }
        }
        bool jud = 1;
        // if(!x1.size())
        //     cout << "NO\n";
        for (int i = 0; i < x1.size(); i++)
        {
            if (get(x1[i]) == get(x2[i]))
            {
                jud = 0;
                cout << "NO\n";
                break;
            }
        }
        if (jud)
            cout << "YES\n";
    }
}

这里要加一个cin和cout的解绑,否则有一个测试点会过不去,就比较寄,感觉,应该是一个要形成习惯的地方

Supermarket

按利润大小从大到小排序,建立一个关于天数的并查集,让商品尽可能晚的卖出(决策包容性),把商品安排在过期前的空白天卖出,如无空白天则不卖

“扩展域”与”边带权”的并查集

并查集实质上是由若干棵树构成的森林,我们可以在树中的每条边上记录一个权值,用d[x]保存结点x到父节点发[下]之间的边权

在每次路径压缩后,每个访问过的结点都会直接指向树根,如果我们同时更新这些结点的d值,就可以利用路径压缩过程来统计每个节点到树根之间的路径上的一些信息.

int get(int x)
{
    if(x == fa[x]) return x;
    int root = get(fa[x]);
    d[x] += d[fa[x]];
    return fa[x] = root;
}
void merge(int x, int y)
{
    x = get(x), y =get(y);
    if(x == y) return; //纠错
    fa[x] = y, d[x] = size[y];
    size[y] += size[x];
}
银河英雄传说

这道题是一道比较典型的并查集题,因为它没有在某一列添加之类的操作,所以合并之后,可以看做被合并的那一列消失了.因此可以用并查集来做,每条边带权值1,树上两点之间的距离减1就是两者之间间隔的战舰数量.

这道题要给上面的Merge纠下错,就是,如果x和y已经在同一个集合了,需要直接结束函数,不要再合并

#include <bits/stdc++.h>
using namespace std;
int fa[30005], d[30004], sizee[30004];
int n, m;
int get(int x)
{
    if (x == fa[x])
        return x;
    int root = get(fa[x]);
    d[x] += d[fa[x]];
    return fa[x] = root;
}
void merge(int x, int y)
{
    x = get(x), y = get(y);
    if(x == y)
        return;
    fa[x] = y, d[x] = sizee[y];
    sizee[y] += sizee[x];
}
int main()
{
    // std::ios::sync_with_stdio(false);
    // std::cin.tie(0);
    cin >> m;
    for (int i = 0; i <= 30000; i++)
    {
        fa[i] = i;
        d[i] = 0;
        sizee[i] = 1;
    }
    while (m--)
    {
        char c;
        int a, b;
        cin >> c >> a >> b;
        if (c == 'M')
            merge(a, b);
        else if (get(a) == get(b))
            cout <<(( a == b )? abs(d[a] - d[b]): abs(d[a] - d[b]) - 1) << '\n';
        else
            cout << "-1\n";
    }
}
Parity game

首先呢,分析这道题的思路,可以看出和之前的题有相似之处,但也有不同(更难)的地方,就是他是一个数组区间(看似连续),以及它的传递关系比较复杂

首先解决数组状,经过分析发现,同样可以变成离散状,因为总数量不大,M个指令,功产生2M个区间,且能判断出来的肯定是连续的区间,这也就可以用边带权的并查集的思想,通过xor判断区间内的奇偶性

#include <bits/stdc++.h>
using namespace std;
struct
{
    int l, r, ans;
} query[10010];
int a[20010], fa[20010], d[20010], n, m, t;
void read_discrete()
{
    cin >> n >> m;
    for (int i = 1; i <= m; i++)
    {
        char str[5];
        cin >> query[i].l >> query[i].r >> str;
        query[i].ans = (str[0] == 'o' ? 1 : 0);
        a[++t] = query[i].l - 1;
        a[++t] = query[i].r;
    }
    sort(a + 1, a + t + 1);
    if (a + t - 1 >= a + 1)//这里要判断一下,增强鲁棒性
        n = unique(a + 1, a + t - 1) - a - 1; // unique是去重函数,把重复值都放在末尾,并返回去重之后的尾地址(使用前需要先排序)
}
int get(int x)
{
    if (x == fa[x])
        return x;
    int root = get(fa[x]);
    d[x] ^= d[fa[x]];
    return fa[x] = root;
}
int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    read_discrete();
    for (int i = 1; i <= n; i++)
        fa[i] = i;
    for (int i = 1; i <= m; i++)
    {
        int x = lower_bound(a + 1, a + n + 1, query[i].l - 1) - a;
        int y = lower_bound(a + 1, a + n + 1, query[i].r) - a; // 查找左右区间对应的哈希后的值
        int p = get(x), q = get(y);
        if (p == q)
        {
            if ((d[x] ^ d[y]) != query[i].ans)
            {
                cout << i - 1 << '\n';
                return 0;
            }
        }
        else
            fa[p] = q, d[p] = d[x] ^ d[y] ^ query[i].ans;
    }
    cout << m << endl;
}

有一个特殊情况是给出的输入数据为1,0,在这时,unique函数因为第二个参数地址小于第一个参数而报错,所以要加一个if判断

image-20230303112741970

食物链

首先构造一个环状的食物链,采用扩展域的并查集解决,将每个节点分为三个节点,同类域,捕食域和天敌域,然后根据食物链的逻辑关系对每句话进行合并,在此之前还要判断真假

image-20230303114249259

#include <bits/stdc++.h>
using namespace std;
int tiandi[4] = {0, 3, 1, 2};
int bushi[4] = {0, 2, 3, 1};
int n, k;
int fa[150005];
int get(int x)
{
    if (x == fa[x])
        return x;
    return fa[x] = get(fa[x]);
}
void merge(int x, int y)
{
    fa[get(x)] = get(y);
}
int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    cin >> n >> k;
    for (int i = 1; i <= 3 * n; i++)
        fa[i] = i;
    int num = 0;
    while (k--)
    {
        int d, a, b;
        cin >> d >> a >> b;
        if (a > n || b > n || (d == 2 && a == b))
        {
            num++;
            continue;
        }
        else
            ;
        if (d == 1)
        {
            if (get(a + n) == get(b) || get(a) == get(b + n))
            {
                num++;
                continue;
            }
        }
        else
        {
            if (get(a) == get(b) || get(a) == get(b + n))
            {
                num++;
                continue;
            }
        }
        if (d == 1)
        {
            merge(a, b);
            merge(a + n, b + n);
            merge(a + n + n, b + n + n);
        }
        else
        {
            merge(a + n, b);
            merge(a, b + n + n);
            merge(a + n + n, b + n);
        }
    }
    cout << num;
}

Related Posts