小指针
2022/10/22阅读：34主题：凝夜紫
【数据结构】并查集的实战应用
前置知识
看完必会的并查集入门攻略。本文是上篇文章的延伸，「并查集」的实战应用篇。
「目录」
AcWing 1250. 格子游戏：二维坐标的并查集裸替，主要考察二维坐标转一维。
AcWing 1252. 搭配购买：使用并查集把相同集合的多个物品看做一个整体，方便使用01背包。
AcWing 237. 程序自动分析：带有离散化的并查集。
AcWing 238. 银河英雄传说：维护额外信息（距离和个数）的并查集。
AcWing 239. 奇偶游戏：综合应用。带有边权的并查集和带有扩展域的并查集，同时也应用了离散化。
AcWing 1250. 格子游戏
Alice和Bob玩了一个古老的游戏：首先画一个n×n的点阵（下图n=3）。接着，他们两个轮流在相邻的点之间画上红边和蓝边：
直到围成一个封闭的圈（面积不必为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，我们「先把所有相等关系的数据合并到一个集合中」，那么「在所有的不等关系的数据中，只要两个数据在同一个集合内，就说明发生冲突」，比如x1和x4。
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<int, int> 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条指令，每条指令格式为以下两种之一：
M i j，表示让第i号战舰所在列的全部战舰保持原有顺序，接在第j号战舰所在列的尾部。C i j，表示询问第i号战舰与第j号战舰当前是否处于同一列中，如果在同一列中，它们之间间隔了多少艘战舰。现在需要你编写一个程序，处理一系列的指令。
「输入格式」
第一行包含整数T，表示共有T条指令。接下来T行，每行一个指令，指令有两种形式：
M i j或C 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]) - 1, 0) << 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，以及回答
even或odd，用以描述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的个数的奇偶数组。则有：
-
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]也应该是奇数。
-
S[L,R]有奇数个1，等价于sum[L-1]与sum[R]的奇偶性不同。与上面同理。
注意在上面的思路中，我们并没有求出整个sum数组，只是把sum[3]和sum[6]看做一个变量。
如此，我们就构造出了「数据的传递关系」，因此，我们就可以参考上题的思路，使用并查集来解决。
但是与上题相比，本题有三种关系：
-
如果x1和x2的奇偶性相同，x2和x3奇偶性也相同，那么x1和x3奇偶性相同；
-
如果x1和x3的奇偶性相同，x2和x3奇偶性不同，那么x1和x3奇偶性不同；
-
如果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]的奇偶性不同。
综上，我们总结一下本题的思路：
-
对于给定的每个区间，我们判断sum[L]和sum[R]是否属于一个集合（奇偶性关系已知）。
-
属于一个集合的话，判断他们在集合内的奇偶关系与给出的奇偶关系是否相同，如果不相同，说明出现矛盾，小A说谎了。
-
如果不属于一个集合，则将两个数据合并。
带扩展域的并查集
我们把变量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到根节点的关系就由三部分组成：
-
x到x的原根节点p[x]，这部分就是d[x]；
-
x的原根节点p[x]到y，也就是
d[p[x]]我们是不知道的，但是我们知道合并后的结果，假设合并后的结果是t，那么就有t=d[x]^d[y]^d[p[x]]，如此，我们就推出了d[p[x]]=d[x]^d[y]^t； -
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<int, int> 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<int, int> 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」
作者介绍