小指针

V1

2022/10/22阅读:25主题:凝夜紫

【数据结构】并查集的实战应用

前置知识

看完必会的并查集入门攻略。本文是上篇文章的延伸,并查集的实战应用篇。

目录

AcWing 1250. 格子游戏:二维坐标的并查集裸替,主要考察二维坐标转一维。

AcWing 1252. 搭配购买:使用并查集把相同集合的多个物品看做一个整体,方便使用01背包。

AcWing 237. 程序自动分析:带有离散化的并查集。

AcWing 238. 银河英雄传说:维护额外信息(距离和个数)的并查集。

AcWing 239. 奇偶游戏:综合应用。带有边权的并查集和带有扩展域的并查集,同时也应用了离散化。

AcWing 1250. 格子游戏

Alice和Bob玩了一个古老的游戏:首先画一个n×n的点阵(下图n=3)。接着,他们两个轮流在相邻的点之间画上红边和蓝边:1.png直到围成一个封闭的圈(面积不必为1)为止,“封圈”的那个人就是赢家。因为棋盘实在是太大了,他们的游戏实在是太长了!他们甚至在游戏中都不知道谁赢得了游戏。于是请你写一个程序,帮助他们计算他们是否结束了游戏?

输入格式

输入数据第一行为两个整数n和m。n表示点阵的大小,m表示一共画了m条线。以后m行,每行首先有两个数字(x,y),代表了画线的起点坐标,接着用空格隔开一个字符,假如字符是D,则是向下连一条边,如果是R就是向右连一条边。输入数据不会有重复的边且保证正确。

输出格式

输出一行:在第几步的时候结束。假如mm步之后也没有结束,则输出一行“draw”。

数据范围

1≤n≤200,
1≤m≤24000

输入样例

3 5
1 1 D
1 1 R
1 2 D
2 1 R
2 2 D

输出样例

4

题目描述

在一个n*n的点阵上画边,一人画一次,问什么时候可以得到一个封闭的矩形。

题目分析

一人一画的规则有点像博弈论的问题,但是读到最后,我们发现并没有问,最后赢的人是谁,而是问什么时候完成封闭矩形的

这样一来就比较简单了。我们可以使用并查集的思路来解决。

初始的时候,每个点都是单独属于一个集合,把两点连接一条边看做是把两点加入到一个集合里。这样一来,假如连完边之后,形成了一个矩形,说明在连边之前,这两个点一定已经在一个集合中

因此,本题其实只需要在合并之前,判断一下两个点是否在同一个集合,就可以知道连完之后会不会出现封闭矩阵。

Code

实现的时候,需要注意的一点是:题目给出的点是二维的,我们需要转换成一维。

二维转一维的公式是:x坐标 * n + y坐标(其中x和y必须从0开始)。

#include <iostream>
#include <cstring>

using namespace std;

const int N = 40010, M = 24010;
int n, m;
int p[N], res;

int find(int x) {
    if (p[x] != x) p[x] = find(p[x]);
    return p[x];
}

// 二维点坐标变成一维
int get(int x, int y) {
    return x * n + y;
}

int main() {
    cin >> n >> m;
    for (int i = 0; i <= n * n; i ++ ) p[i] = i;
    for (int i = 1; i <= m; i ++ ) {
        int x, y;
        char t;
        cin >> x >> y >> t;
        // 二维转一维 坐标必须从0开始 不然不满足公式
        x -- , y -- ;
        int a = get(x, y); 
        int b;
        if (t == 'D') b = get(x + 1, y);
        else b = get(x, y + 1);
        int pa = find(a), pb = find(b);
        // 两个点在同一集合 则连边后形成封闭矩阵
        if (pa == pb) {
            res = i;
            break;
        }
        p[pa] = pb; // 不在同一集合 合并两条边
    }
    if (!res) puts("draw");
    else cout << res << endl;
    return 0;
}

AcWing 1252. 搭配购买

Joe觉得云朵很美,决定去山上的商店买一些云朵。商店里有n朵云,云朵被编号为1,2,…,n并且每朵云都有一个价值。但是商店老板跟他说,一些云朵要搭配来买才好,所以买一朵云则与这朵云有搭配的云都要买。但是Joe的钱有限,所以他希望买的价值越多越好。

输入格式

第1行包含三个整数n,m,w表示有n朵云,m个搭配,Joe有w的钱。第2∼n+1行,每行两个整数ci,di表示i朵云的价钱和价值。第n+2∼n+1+m行,每行两个整数ui,vi表示买ui就必须买vi,同理,如果买vi就必须买ui。

输出格式

一行,表示可以获得的最大价值。

数据范围

1≤n≤10000,
0≤m≤5000,
1≤w≤10000,
1≤ci≤5000,
1≤di≤100,
1≤ui,vi≤n

输入样例

5 3 10
3 10
3 10
3 10
5 100
10 1
1 3
3 2
4 2

输出样例

1

题目描述

(买云朵的故事真是太浪漫啦~~)

一些云朵需要搭配起来购买,总共有n朵云,m个搭配,Joe同学有w块钱,每个云朵都有价钱和价值两种属性,问怎么买才能获得最大价值的云朵。

题目分析

一眼看上去非常的像有依赖的背包问题,但是我们仔细的读题,会发现与依赖背包还是不太一样,对于本题来说,如果有一个云朵被买,那么所有与该云朵搭配的云朵都需要一起被买(而依赖背包中是只有父节点被购买,才需要子节点也购买,反过来,子节点购买,是不需要购买父节点的),这就启发我们,把所有搭配的云朵看做一个集合(并查集的集),然后把每个集合作为一个商品,这样本题就变成了01背包问题。

Code

#include <iostream>
#include <cstring>

using namespace std;

const int N = 10010;
int p[N], w[N], v[N], f[N];
int n, m, money;

int find(int x) {
    if (p[x] != x) p[x] = find(p[x]);
    return p[x];
}

int main() {
    cin >> n >> m >> money;
    for (int i = 1; i <= n; i ++ ) p[i] = i;
    for (int i = 1; i <= n; i ++ ) cin >> v[i] >> w[i];
    
    while (m -- ) {
        int a, b;
        cin >> a >> b;
        int pa = find(a); int pb = find(b);
        // 合并一个集合里的云朵 价格和价值 别忘记合并
        if (pa != pb) {
            w[pa] += w[pb];
            v[pa] += v[pb];
            p[pb] = pa;
        }
    }
    // 01背包模板
    for (int i = 1; i <= n; i ++ ) {
        if (p[i] == i)
            for (int j = money; j >= v[i]; j -- )
                f[j] = max(f[j], f[j - v[i]] + w[i]);
    }
    cout << f[money] << endl;
    return 0;
}

AcWing 237. 程序自动分析

在实现程序自动分析的过程中,常常需要判定一些约束条件是否能被同时满足。

考虑一个约束满足问题的简化版本:假设 x1,x2,x3,… 代表程序中出现的变量,给定 n 个形如 xi=xj 或 xi≠xj 的变量相等/不等的约束条件,请判定是否可以分别为每一个变量赋予恰当的值,使得上述所有约束条件同时被满足。

例如,一个问题中的约束条件为:x1=x2,x2=x3,x3=x4,x1≠x4,这些约束条件显然是不可能同时被满足的,因此这个问题应判定为不可被满足。

现在给出一些约束满足问题,请分别对它们进行判定。

输入格式 输入文件的第 1 行包含 1 个正整数 t,表示需要判定的问题个数,注意这些问题之间是相互独立的。

对于每个问题,包含若干行:

第 1 行包含 1 个正整数 n,表示该问题中需要被满足的约束条件个数。

接下来 n 行,每行包括 3 个整数 i,j,e,描述 1 个相等/不等的约束条件,相邻整数之间用单个空格隔开。若 e=1,则该约束条件为 xi=xj;若 e=0,则该约束条件为 xi≠xj。

输出格式 输出文件包括 t 行。

输出文件的第 k 行输出一个字符串 YES 或者 NO,YES 表示输入中的第 k 个问题判定为可以被满足,NO 表示不可被满足。

数据范围
1≤n≤10^5
1≤i,j≤10^9

输入样例

2
1 2 1
1 2 0
2
1 2 1
2 1 1

输出样例

NO
YES

题目分析

给出一些约束条件,这些约束条件分为两个种类,一种是等于,一种是不等于,问题是给出的约束条件能否同时满足

题目分析

本题第一眼看上去,有些像差分约束问题,但是我们发现本题的约束条件只有两种,一种等于,一种不等于,所以我们完全没必要把约束条件转换成图。

我们发现这两种类型的数据具有明显的传递关系,那就可以把这两种关系类型的数据用集合维护起来,等于号的在一个集合,不等于号的在另一个集合,这样只要集合出现冲突就说明这个问题可以被判定为不满足条件。

而维护具有传递关系的集合,我们就可以使用并查集

例如题面给出的示例:x1=x2,x2=x3,x3=x4,x1≠x4,我们先把所有相等关系的数据合并到一个集合中,那么在所有的不等关系的数据中,只要两个数据在同一个集合内,就说明发生冲突,比如x1x4

Code

本题虽然看起来是一个并查集的裸题,但是其实难点并不在并查集,而是隐藏在数据范围中。

本题的约束条件数量n总共有 个,每个约束条件有两个数据,也就是说数据最多也就只会有 个,可是单个数据的最大值却达到了 ,那么对于并查集数组来说,就需要 的空间大小,这显然是不可行的。所以,我们需要使用离散化把的单个数据的大小映射到最大为

离散化的作用:当出现数据范围很大,但是能用到的很小的时候,可以使用 离散化 把 数据范围 压缩到 使用范围

比如,本题把单个数据最大 压缩到单个数据最大

离散化一般分为两种:保持数据顺序的离散化不保序的离散化

保序的离散化一般要分为三个步骤:排序、判重、二分。

不保序的离散化比较简单可以使用map或者hash表之类的数据结构实现即可。

(离散化不是本文重点,因此不做过多讲述,代码中有注释。)

#include <iostream>
#include <cstring>
#include <unordered_map>

using namespace std;

const int N = 2000010;
int n, m;
int p[N];
unordered_map<intint> S; // 离散化hash表

struct Query {
    int x, y, e;
}query[N];

// 超级简单的不保序离散化
// 将单个数据范围在1~10^9 压缩到 单个数据范围在1~10^6
int get(int x) {
    // 如果x不在哈希表中 就给它一个映射值。
    if (S.count(x) == 0) S[x] = ++ n;
    return S[x]; // 返回x在哈希表的位置
}

int find(int x) {
    if (p[x] != x) p[x] = find(p[x]);
    return p[x];
}

int main() {
    int T;
    cin >> T;
    while (T -- ) {
        cin >> m;
        n = 0;
        S.clear();
        for (int i = 0; i < m; i ++ ) {
            int a, b, c;
            scanf("%d%d%d", &a, &b, &c);
            query[i] = {get(a), get(b), c};
        }
        for (int i = 1; i <= n; i ++ ) p[i] = i;
        // 合并 所有的 相等约束条件
        for (int i = 0; i < m; i ++ ) {
            if (query[i].e == 1) {
                int pa = find(query[i].x);
                int pb = find(query[i].y);
                p[pa] = pb;
            }
        }
        // 检查不等条件
        bool flag = false;
        for (int i = 0; i < m; i ++ ) {
            if (query[i].e == 0 ) {
                int pa = find(query[i].x);
                int pb = find(query[i].y);
                // 在同一个集合说明相等 与 不等条件冲突
                if (pa == pb) { 
                    flag = true;
                    break;
                }
            }
        }
        if (flag) puts("NO");
        else puts("YES");
    }
    return 0;
}

AcWing 238. 银河英雄传说

有一个划分为N列的星际战场,各列依次编号为1,2,…,N。有N艘战舰,也依次编号为1,2,…,N,其中第i号战舰处于第i列。有T条指令,每条指令格式为以下两种之一:

  1. M i j,表示让第i号战舰所在列的全部战舰保持原有顺序,接在第j号战舰所在列的尾部。
  2. C i j,表示询问第i号战舰与第j号战舰当前是否处于同一列中,如果在同一列中,它们之间间隔了多少艘战舰。

现在需要你编写一个程序,处理一系列的指令。

输入格式

第一行包含整数T,表示共有T条指令。接下来T行,每行一个指令,指令有两种形式:M i jC i j。其中M和C为大写字母表示指令类型,i和j为整数,表示指令涉及的战舰编号。

输出格式

你的程序应当依次对输入的每一条指令进行分析和处理:如果是M i j形式,则表示舰队排列发生了变化,你的程序要注意到这一点,但是不要输出任何信息;如果是C i j形式,你的程序要输出一行,仅包含一个整数,表示在同一列上,第i号战舰与第j号战舰之间布置的战舰数目,如果第i号战舰与第j号战舰当前不在同一列上,则输出−1。

数据范围

N≤30000,T≤500000

输入样例

4
M 2 3
C 1 2
M 2 4
C 4 2

输出样例

-1
1

题目描述

并查集的模型,加了一个题面,有N个集合,初始化时候,每个集合有一个元素。给出两种命令,一种是合并,一种是查询,不过这个合并的规则是必须是a和并到b上,也就a的父节点是b。而查询的也不仅仅是两个数是否在一个集合,而是当两个数据在一个集合的时候输出这两个数据的 之间有多少个数据

本题题面隐性表达了非常重要的一点,那就是本题的所有集合均是,因为所有的合并都是合并到集合的末尾。(后面的分析如果不明白就可以思考一下,集合是链的含义。)

题目分析

比较裸的一个并查集题目。主要的难点在于如何维护并查集中数据的位置

基础篇中,我们已经讲解过,使用size数组维护集合中元素的数量。而本题还需要配合一个另外的数组d,来维护并查集中元素到它的根节点的距离

d[x]:表示集合中的元素x到它的根节点p[x]的距离。

维护这个距离的意义是什么呢?

试想一下,我们想求的是一个集合中a和b之间的距离,那么我们只要知道它俩分别到根节点的距离,用这两个距离做差就求出来了。

比如,x和y在一个集合,x到根节点的距离d[x]=4,而y到根节点的距离d[y]=7,那么很明显它俩之间的数据就是d[x]-d[y]的绝对值减一,也就是它俩之间有两个元素(5和6)

那么,现在的问题就变成了如何维护距离数组d呢?

首先考虑,两个集合的合并,假设我们把集合x合并到了集合y上面。

通过图中,我们能直观的看到合并的情况,当集合px合并到py,那么p[x]到根节点的距离 就是 合并前py中 的所有数据,而合并后,集合px就消失了,只剩下集合py,py中的数据数量就是 两个集合的数量之和

除此之外,在合并的时候,在上面的合并上,我们其实并没有求出每个点到根节点的距离,那么我们就可以在,路径优化的时候,来维护每个节点到根节点的距离。

路径优化维护距离的时候,我们虽然不知道每个距离到根节点的距离,但是我们可以用自底向上的递归,从根节点出发来更新每个节点的距离。

综上,我们就维护出了一个每个元素到根节点的距离的数组d。

Code

#include <iostream>
#include <cstring>

using namespace std;

const int N = 300010;
int n, m, p[N], sz[N], d[N];

// 维护距离的并查集模板
int find(int x) {
    if (p[x] != x) {
        int root = find(p[x]); // 先递归到根节点
        d[x] += d[p[x]];  // 根节点开始累加
        p[x] = root;
    }
    return p[x];
}

int main() {
    cin >> m;
    // 初始化 每个节点到自身的距离为0 
    // 初始化 每个集合中的数据个数为1 也就是根节点自己
    for (int i = 1; i <= N; i ++ )
        p[i] = i, d[i] = 0, sz[i] = 1;
    while (m -- ) {
        int a, b;
        char t;
        cin >> t >> a >> b;
        int pa = find(a), pb = find(b);
        if (t == 'M') {
            // 当两个数据不在一个集合 则合并
            if (pa != pb) {
                // 合并 且维护信息
                p[pa] = pb;
                d[pa] = sz[pb];
                sz[pb] += sz[pa];
            }
        } else {
            if (pa != pb) cout << -1 << endl;
            else {
                // 注意输出的时候 因为减一的关系 可能会负
                // 但是有解情况 最小是0 也就是自己到自己
                cout << max(abs(d[a] - d[b]) - 10) << endl;
            }
        }
    }
    return 0;
}

AcWing 239. 奇偶游戏

小A和小B在玩一个游戏。首先,小A写了一个由0和1组成的序列S,长度为N。然后,小B向小A提出了M个问题。在每个问题中,小B指定两个数l和r,小A回答S[l∼r]中有奇数个1还是偶数个1。机智的小B发现小A有可能在撒谎。例如,小A曾经回答过S[1∼3]中有奇数个1,S[4∼6]中有偶数个1,现在又回答S[1∼6]中有偶数个1,显然这是自相矛盾的。请你帮助小B检查这M个答案,并指出在至少多少个回答之后可以确定小A一定在撒谎。即求出一个最小的k,使得01序列S满足第1∼k个回答,但不满足第1∼k+1个回答。

输入格式

第一行包含一个整数N,表示01序列长度。第二行包含一个整数M,表示问题数量。接下来M行,每行包含一组问答:两个整数l和r,以及回答evenodd,用以描述S[l∼r]中有偶数个1还是奇数个1。

输出格式

输出一个整数k,表示01序列满足第1∼k个回答,但不满足第1∼k+1个回答,如果01序列满足所有回答,则输出问题总数量。

数据范围

N≤109,M≤5000

输入样例

10
5
1 2 even
3 4 odd
5 6 even
1 6 even
7 10 odd

输出样例

3

题目描述

一个有趣的游戏,小A给出一个01序列S,小B问小A一个区间[l,r]内有多少个1。但是小B发现小A可能会说谎,比如小A说区间[1,3]中有奇数个1,[4,6]有偶数个1,那么奇数 加上 偶数 则一定有 奇数个1,也就是区间[1,6]一定有奇数个1,可是小A又说[1,6]有偶数个1,所以小A说谎了。

问题是给出M个回答,问小B在第几个回答的时候发现小A说慌了

题目分析

本题给出的是一个区间的奇偶性,对于整个区间而言是不太好分析的,所以使用类似前缀和的思想,将区间转换为变量

使用sum[i]表示1~i中1的个数的奇偶数组。则有:

  1. S[L,R]有偶数个1,等价于sum[L-1]与sum[R]的奇偶性相同。例如,示例中有S[1,3]有奇数个1,S[4,6]有偶数个1。而区间S[4,6]又可以拆分成sum[3]和sum[6],并且他们两个奇偶性应该相同,而sum[3]就是区间S[1,3]是奇数,所以sum[6]就是区间S[1,6]也应该是奇数。

  2. S[L,R]有奇数个1,等价于sum[L-1]与sum[R]的奇偶性不同。与上面同理。

注意在上面的思路中,我们并没有求出整个sum数组,只是把sum[3]和sum[6]看做一个变量。

如此,我们就构造出了数据的传递关系,因此,我们就可以参考上题的思路,使用并查集来解决。

但是与上题相比,本题有三种关系:

  1. 如果x1和x2的奇偶性相同,x2和x3奇偶性也相同,那么x1和x3奇偶性相同;

  2. 如果x1和x3的奇偶性相同,x2和x3奇偶性不同,那么x1和x3奇偶性不同;

  3. 如果x1和x2的奇偶性不同,x2和x3奇偶性也不同,那么x1和x3的奇偶性相同;

我们神奇的发现,如果把奇偶性相同看做1,不同看做0,那么这不就是异或的运算规则嘛?

对于这种多种传递关系的并查集,一种解决方案是使用带边权的并查集,还有一种解决方案是使用带扩展域的并查集

带边权的并查集

我们可以参考一下上一道题,在上一道题中,同样是判断矛盾,当发现不等式组的两个数据在同一个集合中,我们就认为是矛盾。但是在本题中,我们还需要知道这两个数据在这个集合中的奇偶关系是否什么样的

那么如何维护一个集合中不同数据的关系呢

我们可以让集合中的每个数据都与根节点产生关联,以此间接的使所有的数据关联到一起。

比如:a与根节点奇偶性不同,b与根节点奇偶性相同,则我们可以知道a与b奇偶性不同。

所以,在路径优化的过程中,就可以把每个数据与根节点的关系维护出来,也就是带有边权的并查集

带有边权的并查集,使用一个数组d[x]维护数据x与根节点p[x]相对关系。

在本题中,边权d[x]为0表示与根节点p[x]的奇偶性相同,为1表示与根节点p[x]的奇偶性不同。

综上,我们总结一下本题的思路:

  1. 对于给定的每个区间,我们判断sum[L]和sum[R]是否属于一个集合(奇偶性关系已知)。

  2. 属于一个集合的话,判断他们在集合内的奇偶关系与给出的奇偶关系是否相同,如果不相同,说明出现矛盾,小A说谎了。

  3. 如果不属于一个集合,则将两个数据合并。

带扩展域的并查集

我们把变量X拆分成两个节点,一个是Xodd,一个是Xeven。其中Xodd表示sum[X]是奇数,Xeven表示sum[X]是偶数,我们一般也会把这两个节点分别称为奇数域偶数域

在带扩展域的并查集中,我们要合并的就是这些域,而非数据本身。

假设,题目给出区间[L,R]的奇偶性是ans,并且sum[L-1]和sum[R]离散化之后是x和y,假设,我们让ans为0表示偶数,1表示奇数。

那么当ans等于0的时候,合并Xodd,Yodd,合并Xeven,Yeven,表示当X和Y的奇偶性相同的时候,可以互相推出,既知道X是偶数,则Y也是偶数;知道X是奇数,则Y也是奇数。

当ans等于1的时候,合并Xodd,Yeven,合并Xeven,Yodd,表示当X和Y奇偶性不同的时候,可以互相推出。

我们的想一下,这样做有什么好处呢

我们把使用并查集 维护数据 变成了 维护条件,也就是我们本来维护的是X和Y,现在变成了维护X是偶数,Y是奇数等条件

这样做,当我们知道X与Y的关系之后,如果又知道了Y与Z的关系,那么我们也就知道了X与Z的关系,也就是这些条件具有传递性

比如,通过数据x,y,0推出X和Y的奇偶性相同,再来一个数据y,z,1推出Y和Z奇偶性不同,我们就可以得到x,z,1表示X与Z的奇偶性也是不同的。

那么,我们如何判断矛盾呢

假如两个变量X和Y,有Xodd和Yodd在一个集合,说明两者奇偶性必定相同;如果Xodd和Yeven在一个集合里说明两者奇偶性是不同的,那么如果新数据与之相悖,说明出现了矛盾。

Code

在实现上,由于本题的数据范围也是比较奇怪,N的长度为 ,但是问答M的数量只有 ,因此也需要使用离散化压缩数据。

带边权的并查集

带边权的并查集,在合并时候要更新边权数组d[]。

我们定义d[x]表示的是x到根节点p[x]的关系,d[y]是y到根节点p[y]的关系,那么合并的时候,假如是把x合并到了y上面(以y作为集合根节点),那么x到根节点的关系就由三部分组成:

  1. x到x的原根节点p[x],这部分就是d[x];

  2. x的原根节点p[x]到y,也就是d[p[x]]我们是不知道的,但是我们知道合并后的结果,假设合并后的结果是t,那么就有t=d[x]^d[y]^d[p[x]],如此,我们就推出了d[p[x]]=d[x]^d[y]^t

  3. y到根节点p[y],这部分就是d[y];

我们把这三部分全部异或起来,就得到了合并后的d[x]。

#include <iostream>
#include <cstring>
#include <unordered_map>

using namespace std;

const int N = 20010;
int n, m;
int p[N], d[N];
unordered_map<intint> S;

int find(int x) {
    // 带权并查集的路径压缩 必须注意细节
    // 一定 先计算边权 再压缩
    if (p[x] != x) {
        int root = find(p[x]);
        d[x] ^= d[p[x]];
        p[x] = root;
    }
    return p[x];
}

int get(int x) {
    if (S.count(x) == 0) S[x] = ++ n;
    return S[x];
}

int main() {
    cin >> n >> m;
    n = 0;
    for (int i = 0; i < N; i ++ ) p[i] = i;
    int res = m; // 没有矛盾输出问题的数量
    for (int i = 0; i < m; i ++ ) {
        int a, b;
        string c;
        cin >> a >> b >> c;
        // 获取离散化后的sum[L-1]和sum[R]
        a = get(a - 1), b = get(b);
        int t = 0// 0表示偶数个1
        if (c == "odd") t = 1// 1表示有奇数个1
        int pa = find(a), pb = find(b);
        // 如果两个数据的奇偶关系已知
        if (pa == pb) {
            // 判断他们的奇偶关系 是否和本次数据相同
            if ((d[a] ^ d[b]) != t) {
                res = i;
                break;
            }
        } else {
            p[pa] = pb;
            // 并查集到根
            d[pa] = d[a] ^ d[b] ^ t;
        }
    }
    cout << res << endl;
    return 0;
}

带扩展域的并查集

在实现上,我们如何表示两个点呢?

可以直接用两个不同的数,假如数据为X,那么我们可以让X本身来表示Xeven,用X+Base来表示Xodd(这里的Base为数据总量除以2,所以X+Base是一个一定不在本题使用范围内的数,因此保证了数据不会重复)。

#include <iostream>
#include <cstring>
#include <unordered_map>

using namespace std;

const int N = 20010, Base = N / 2;
int n, m;
int p[N], d[N];
unordered_map<intint> S;

int find(int x) {
    if (p[x] != x) p[x] = find(p[x]);
    return p[x];
}

int get(int x) {
    if (S.count(x) == 0) S[x] = ++ n;
    return S[x];
}

int main() {
    cin >> n >> m;
    n = 0;
    for (int i = 0; i < N; i ++ ) p[i] = i;
    int res = m; // 没有矛盾输出问题的数量
    for (int i = 0; i < m; i ++ ) {
        int a, b;
        string c;
        cin >> a >> b >> c;
        // 获取离散化后的sum[L-1]和sum[R]
        a = get(a - 1), b = get(b);
        int t = 0// 0表示偶数个1
        // 假如给出数据是X和Y是偶数关系
        // 则有Xodd和Yodd 在一个集合 Xeven和Yeven在一个集合
        if (c == "even") {
            // 如果Xodd和Yeven在一个集合 一定矛盾
            if (find(a + Base) == find(b)) {
                res = i;
                break;
            }
            p[find(a)] = p[find(b)]; // Xodd和Yodd合并到一个集合
            p[find(a + Base)] = p[find(b + Base)]; // Xeven和Yeven合并到一个集合
        } else {
            // 反之,则相反
            if (find(a) == find(b)) {
                res = i;
                break;
            }
            p[find(a)] = p[find(b + Base)]; // Xeven和Yodd在一个集合
            p[find(a + Base)] = p[find(b)]; // Xodd 和 Yeven在一个集合
        }
    }
    cout << res << endl;
    return 0;
}

END

分类:

后端

标签:

数据结构与算法

作者介绍

小指针
V1