算法基础-并查集

并查集

1.1双亲表⽰法

1.2并查集的概念

1.3并查集的实现

1.3.1初始化

代码实现：

#include <iostream> using namespace std; // 定义数组最大容量：100万+10（留余量避免越界） const int N = 1e6 + 10; // n表示需要管理的元素总数 int n; // fa数组：fa[i]代表元素i的父节点（组长），双亲表示法核心数组 int fa[N]; // 初始化并查集函数：让每个元素的父节点都是自己（自成一组） void init() { // 遍历1到n的所有元素 for(int i = 1; i <= n; i++) { // 每个元素初始时组长是自己 fa[i] = i; } } // 主函数示例：演示如何使用初始化函数 int main() { // 示例：假设要管理5个元素 n = 5; // 调用初始化函数 init(); // 打印初始化后的fa数组（验证结果） cout << "初始化后fa数组：" << endl; for(int i = 1; i <= n; i++) { cout << "fa[" << i << "] = " << fa[i] << endl; } return 0; }

1.3.2查询操作

查询操作是并查集的核⼼操作，其余所有的操作都是基于查询操作实现的！

找到元素x所属的集合：

• ⼀直向上找爸爸~

代码实现：

int find(int x) { if(fa[x] == x) return x; return find(fa[x]); // 一行实现 // return fa[x] == x ? x : find(fa[x]); }

1.3.3合并操作

代码实现：

// 合并操作 void un(int x, int y) // 注意，函数名字不能⽤ union，因为它是 C++ 的关键字 { int fx = find(x); int fy = find(y); fa[fx] = fy; }

1.3.4判断操作

代码实现：

// 判断是否在同⼀集合 bool issame(int x, int y) { return find(x) == find(y); }

1.4并查集的优化

代码实现：

// 找根节点 - 路径压缩 int find(int x) { if(fa[x] == x) return x; return fa[x] = find(fa[x]); // ⼀⾏实现 return fa[x] == x ? x : fa[x] = find(fa[x]); }

还有⼀种优化⽅式是按秩合并，但是基本上不⽤按秩合并，并查集的时间复杂度就很优秀了。感兴趣 的同学可以搜⼀下按秩合并，按照⼤家现在的⽔平，应该很容易就能看懂~

在《算法导论》中有严格的证明，并查集查询根节点的最坏时间复杂度为O(α(n)) ，是⼀个很⼩的常 数。因此，并查集查询以及合并的效率近似可以看成O(1)。

1.5普通并查集

1.5.1【模板】并查集

题目背景

本题数据范围已经更新到 1≤N≤2×105，1≤M≤106。

题目描述

如题，现在有一个并查集，你需要完成合并和查询操作。

输入格式

第一行包含两个整数 N,M ,表示共有 N 个元素和 M 个操作。

接下来 M 行，每行包含三个整数 Zi​,Xi​,Yi​ 。

当 Zi​=1 时，将 Xi​ 与 Yi​ 所在的集合合并。

当 Zi​=2 时，输出 Xi​ 与 Yi​ 是否在同一集合内，是的输出Y；否则输出N。

输出格式

对于每一个 Zi​=2 的操作，都有一行输出，每行包含一个大写字母，为Y或者N。

输入输出样例

输入 #1复制

4 7 2 1 2 1 1 2 2 1 2 1 3 4 2 1 4 1 2 3 2 1 4

输出 #1复制

N Y N Y

说明/提示

对于 15% 的数据，N≤10，M≤20。

对于 35% 的数据，N≤100，M≤103。

对于 50% 的数据，1≤N≤104，1≤M≤2×105。

对于 100% 的数据，1≤N≤2×105，1≤M≤106，1≤Xi​,Yi​≤N，Zi​∈{1,2}。

【解法】

【参考代码】

#include <iostream> using namespace std; const int N = 2e5 + 10; // 数组最大容量：20万+10（留余量） int n; // 元素总数（比如示例里n=4） int fa[N]; // fa[i]：元素i的父节点（组长） // find函数：找元素x的“最终组长”（根节点），并做路径压缩（提速） int find(int x) { // 如果x的父节点是自己，说明x就是组长，直接返回 if(fa[x] == x) return x; // 否则：递归找x父节点的组长，同时把x的父节点直接指向组长（路径压缩） return fa[x] = find(fa[x]); } int main() { int T; // T是操作总数（示例里T=7） cin >> n >> T; // 初始化并查集：每个元素的组长都是自己 for(int i = 1; i <= n; i++) fa[i] = i; // 遍历所有操作（T--：执行T次，每次减1） while(T--) { int z, x, y; // z是操作类型，x、y是操作的元素 cin >> z >> x >> y; if(z == 1) // 操作1：合并x和y所在的集合 { int fx = find(x); // 找x的最终组长 int fy = find(y); // 找y的最终组长 fa[fx] = fy; // 把x的组长的父节点设为y的组长（合并两组） } else // 操作2：查询x和y是否同组 { // 若x和y的最终组长相同，说明同组→输出Y，否则输出N if(find(x) == find(y)) cout << "Y" << endl; else cout << "N" << endl; } } return 0; }

1.5.2亲戚

若某个家族人员过于庞大，要判断两个是否是亲戚，确实还很不容易，现在给出某个亲戚关系图，求任意给出的两个人是否具有亲戚关系。

题目描述

规定：x 和 y 是亲戚，y 和 z 是亲戚，那么 x 和 z 也是亲戚。如果 x，y 是亲戚，那么 x 的亲戚都是 y 的亲戚，y 的亲戚也都是 x 的亲戚。

输入格式

第一行：三个整数 n,m,p，（n,m,p≤5000），分别表示有 n 个人，m 个亲戚关系，询问 p 对亲戚关系。

以下 m 行：每行两个数 Mi​，Mj​，1≤Mi​, Mj​≤n，表示 Mi​ 和 Mj​ 具有亲戚关系。

接下来 p 行：每行两个数 Pi​,Pj​，询问 Pi​ 和 Pj​ 是否具有亲戚关系。

输出格式

p 行，每行一个Yes或No。表示第 i 个询问的答案为“具有”或“不具有”亲戚关系。

输入输出样例

输入 #1复制

6 5 3 1 2 1 5 3 4 5 2 1 3 1 4 2 3 5 6

输出 #1复制

Yes Yes No

【解法】

【参考代码】

#include <iostream> using namespace std; const int N = 5010; // 数组最大容量：5010（因为n≤5000，留10个余量） int n, m, p; // n=人数，m=亲戚关系数，p=询问数 int fa[N]; // fa[i]：第i个人的“亲戚组长”（根节点） // find函数：找第x个人的最终组长（路径压缩，提速） // 三元运算符：fa[x]==x就返回x，否则递归找并压缩路径 int find(int x) { return fa[x] == x ? x : fa[x] = find(fa[x]); } // un函数：合并x和y的亲戚组（un是union的缩写，因为union是关键字不能用） void un(int x, int y) { int fx = find(x); // 找x的最终组长 int fy = find(y); // 找y的最终组长 fa[fy] = fx; // 把y的组长的父节点设为x的组长（合并两组） } // issame函数：判断x和y是不是亲戚（最终组长相同就是亲戚） bool issame(int x, int y) { return find(x) == find(y); } int main() { cin >> n >> m >> p; // 初始化并查集：每个人的组长都是自己（初始无亲戚） for(int i = 1; i <= n; i++) fa[i] = i; // 处理m组亲戚关系：合并对应的人 while(m--) { int x, y; cin >> x >> y; un(x, y); // 合并x和y的亲戚组 } // 处理p个询问：判断是不是亲戚，输出Yes/No while(p--) { int x, y; cin >> x >> y; if(issame(x, y)) cout << "Yes\n"; // 是亲戚输出Yes else cout << "No\n"; // 不是输出No } return 0; }

1.5.3Lake Counting

由于最近的降雨，水在农夫约翰的田地里积聚了。田地可以表示为一个 N×M 的矩形（1≤N≤100；1≤M≤100）。每个方格中要么是水（W），要么是干地（.）。农夫约翰想要弄清楚他的田地里形成了多少个水塘。一个水塘是由连通的水方格组成的，其中一个方格被认为与它的八个邻居相邻。给定农夫约翰田地的示意图，确定他有多少个水塘。

输入格式

第 1 行：两个用空格分隔的整数：N 和 M。

第 2 行到第 N+1 行：每行 M 个字符，表示农夫约翰田地的一行。

每个字符要么是W，要么是.。

字符之间没有空格。

输出格式

第 1 行：农夫约翰田地中的水塘数量。

显示翻译

题意翻译

输入输出样例

输入 #1复制

10 12 W........WW. .WWW.....WWW ....WW...WW. .........WW. .........W.. ..W......W.. .W.W.....WW. W.W.W.....W. .W.W......W. ..W.......W.

输出 #1复制

3

说明/提示

输出详情：共有三个水塘：一个在左上角，一个在左下角，还有一个沿着右侧。

（由 ChatGPT 4o 翻译）

【解法】

【参考代码】

#include <iostream> using namespace std; const int N = 110; // 网格最大100×100，留10个余量 int n, m; // n=行数，m=列数（示例里n=10，m=12） char a[N][N]; // 存储网格：a[i][j]是第i行第j列的字符（W/.） int fa[N * N]; // 并查集数组：fa[编号] = 该位置的组长（编号= i*m + j） // 方向数组：只查4个关键方向（右、下、右下、左下），避免重复合并 // dx[k]是行偏移，dy[k]是列偏移 int dx[] = {0, 1, 1, 1}; // 行：0（同列）、1（下一行）、1（下一行）、1（下一行） int dy[] = {1, 1, 0, -1}; // 列：1（右）、1（右下）、0（下）、-1（左下） // find函数：找位置编号x的最终组长（路径压缩） // 三元运算符：如果x的组长是自己，返回x；否则递归找并压缩路径 int find(int x) { return fa[x] == x ? x : fa[x] = find(fa[x]); } // un函数：合并两个位置的集合（x和y是一维编号） void un(int x, int y) { // 把x的组长的父节点设为y的组长 → 合并两个集合 fa[find(x)] = find(y); } int main() { cin >> n >> m; // 读入行数n和列数m // 读入网格：逐行逐列存字符（W/.） for(int i = 0; i < n; i++) for(int j = 0; j < m; j++) cin >> a[i][j]; // 初始化并查集：每个位置的组长都是自己（不管是W还是.） for(int i = 0; i < n * m; i++) fa[i] = i; // 遍历每个网格位置 for(int i = 0; i < n; i++) // 遍历第i行 { for(int j = 0; j < m; j++) // 遍历第j列 { if(a[i][j] == '.') continue; // 是旱地，跳过 // 检查4个关键方向的网格 for(int k = 0; k < 4; k++) { // 计算目标位置的行x、列y int x = i + dx[k]; int y = j + dy[k]; // 边界判断：y≥0（列不越左界）+ x<n（行不越下界） + 目标位置是W if(x < n && y >= 0 && a[x][y] == 'W') { // 把当前位置（i,j）和目标位置（x,y）合并 // 一维编号：i*m+j（当前）、x*m+y（目标） un(i * m + j, x * m + y); } } } } // 统计水坑数：遍历所有位置，数“是W且组长是自己”的数量 int ret = 0; // ret存水坑数，初始为0 for(int i = 0; i < n * m; i++) { // 一维编号转二维坐标：x=行，y=列 int x = i / m; // 行号 = 编号 ÷ 列数（比如i=12，m=12 → x=1） int y = i % m; // 列号 = 编号 % 列数（比如i=12，m=12 → y=0） // 如果该位置是W，且组长是自己 → 是一个独立水坑 if(a[x][y] == 'W' && fa[i] == i) ret++; } cout << ret << endl; // 输出水坑数 return 0; }

1.5.4程序⾃动分析

题目描述

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

考虑一个约束满足问题的简化版本：假设 x1​,x2​,x3​,⋯ 代表程序中出现的变量，给定 n 个形如 xi​=xj​ 或 xi​=xj​ 的变量相等/不等的约束条件，请判定是否可以分别为每一个变量赋予恰当的值，使得上述所有约束条件同时被满足。例如，一个问题中的约束条件为：x1​=x2​,x2​=x3​,x3​=x4​,x4​=x1​，这些约束条件显然是不可能同时被满足的，因此这个问题应判定为不可被满足。

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

输入格式

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

对于每个问题，包含若干行：

第一行包含一个正整数 n，表示该问题中需要被满足的约束条件个数。接下来 n 行，每行包括三个整数 i,j,e，描述一个相等/不等的约束条件，相邻整数之间用单个空格隔开。若 e=1，则该约束条件为 xi​=xj​。若e=0，则该约束条件为 xi​=xj​。

输出格式

输出包括 t 行。

输出文件的第 k 行输出一个字符串YES或者NO（字母全部大写），YES表示输入中的第 k 个问题判定为可以被满足，NO表示不可被满足。

输入输出样例

输入 #1复制

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

输出 #1复制

NO YES

输入 #2复制

2 3 1 2 1 2 3 1 3 1 1 4 1 2 1 2 3 1 3 4 1 1 4 0

输出 #2复制

YES NO

说明/提示

【样例解释1】

在第一个问题中，约束条件为：x1​=x2​,x1​=x2​。这两个约束条件互相矛盾，因此不可被同时满足。

在第二个问题中，约束条件为：x1​=x2​,x1​=x2​。这两个约束条件是等价的，可以被同时满足。

【样例说明2】

在第一个问题中，约束条件有三个：x1​=x2​,x2​=x3​,x3​=x1​。只需赋值使得 x1​=x2​=x3​，即可同时满足所有的约束条件。

在第二个问题中，约束条件有四个：x1​=x2​,x2​=x3​,x3​=x4​,x4​=x1​。由前三个约束条件可以推出 x1​=x2​=x3​=x4​，然而最后一个约束条件却要求 x1​=x4​，因此不可被满足。

【数据范围】

所有测试数据的范围和特点如下表所示：

【解法】

【参考代码】

#include <iostream> #include <unordered_map> // 哈希表，用于离散化映射 #include <algorithm> // 排序，离散化需要 using namespace std; const int N = 1e5 + 10; // 约束条件最多10万条 int n; // 每个问题的约束数 // 存储每个约束条件：x=变量i，y=变量j，e=1（相等）/0（不等） struct node { int x, y, e; }a[N]; // 离散化相关变量 int pos; // 记录所有出现过的变量编号数量 int disc[N * 2]; // 存储所有出现过的变量编号（去重前） unordered_map<int, int> mp; // 映射表：原编号→离散化后的小编号 // 并查集数组 int fa[N * 2]; // find函数：找离散化后编号x的最终组长（路径压缩） int find(int x) { return fa[x] == x ? x : fa[x] = find(fa[x]); } // un函数：合并两个离散化后的编号x和y void un(int x, int y) { fa[find(x)] = find(fa[y]); } // issame函数：判断两个离散化后的编号是否在同一集合 bool issame(int x, int y) { return find(x) == find(y); } // 处理单个问题的函数：返回true（满足）/false（不满足） bool solve() { cin >> n; // 读入当前问题的约束数 // 清空离散化相关数据（多组测试用例，避免干扰） pos = 0; mp.clear(); // 第一步：读入所有约束，收集所有出现过的变量编号 for(int i = 1; i <= n; i++) { cin >> a[i].x >> a[i].y >> a[i].e; // 把变量x、y存入disc数组（后续离散化用） disc[++pos] = a[i].x; disc[++pos] = a[i].y; } // 第二步：离散化（大编号→小编号） // 1. 对disc数组排序（方便去重） sort(disc + 1, disc + 1 + pos); int cnt = 0; // 离散化后的编号（从1开始） for(int i = 1; i <= pos; i++) { int x = disc[i]; if(mp.count(x)) continue; // 已经映射过，跳过（去重） cnt++; // 新的小编号 mp[x] = cnt; // 记录映射关系（比如x1→1） } // 第三步：初始化并查集（离散化后的编号从1到cnt） for(int i = 1; i <= cnt; i++) fa[i] = i; // 第四步：处理所有相等约束（e=1），合并变量 for(int i = 1; i <= n; i++) { int x = a[i].x, y = a[i].y, e = a[i].e; if(e == 1) // 相等约束：合并x和y的离散化编号 un(mp[x], mp[y]); } // 第五步：检查所有不等约束（e=0），判断是否矛盾 for(int i = 1; i <= n; i++) { int x = a[i].x, y = a[i].y, e = a[i].e; if(e == 0) // 不等约束 { // 如果x和y在同一集合（本该不等，却相等）→ 矛盾，返回false if(issame(mp[x], mp[y])) return false; } } // 所有约束都满足，返回true return true; } int main() { int T; cin >> T; // 读入问题个数 while(T--) // 处理每个问题 { if(solve()) // 满足所有约束 cout << "YES" << endl; else // 不满足 cout << "NO" << endl; } return 0; }

1.6扩展域并查集

1.6.1团伙

题目描述

现在有 n 个人，他们之间有两种关系：朋友和敌人。我们知道：

• 一个人的朋友的朋友是朋友
• 一个人的敌人的敌人是朋友

现在要对这些人进行组团。两个人在一个团体内当且仅当这两个人是朋友。请求出这些人中最多可能有的团体数。

输入格式

第一行输入一个整数 n 代表人数。

第二行输入一个整数 m 表示接下来要列出 m 个关系。

接下来 m 行，每行一个字符 opt 和两个整数 p,q，分别代表关系（朋友或敌人），有关系的两个人之中的第一个人和第二个人。其中 opt 有两种可能：

• 如果 opt 为F，则表明 p 和 q 是朋友。
• 如果 opt 为E，则表明 p 和 q 是敌人。

输出格式

一行一个整数代表最多的团体数。

输入输出样例

输入 #1复制

6 4 E 1 4 F 3 5 F 4 6 E 1 2

输出 #1复制

3

说明/提示

对于 100% 的数据，2≤n≤1000，1≤m≤5000，1≤p,q≤n。

【解法】

【参考代码】

#include <iostream> using namespace std; const int N = 1010; // 人数最多1000，扩展域后是2000，留10余量 int n, m; // n=人数，m=关系数 int fa[N * 2]; // 扩展域并查集：1~n是原域（朋友），n+1~2n是敌域（敌人） // find函数：找x的最终组长（路径压缩） int find(int x) { // 三元运算符：x的组长是自己则返回x，否则递归找并压缩路径 return fa[x] == x ? x : fa[x] = find(fa[x]); } // un函数：合并x和y（让y的组长指向x的组长，保证朋友域为父节点） void un(int x, int y) { fa[find(y)] = find(x); } int main() { cin >> n >> m; // 读入人数n和关系数m // 初始化扩展域并查集：1~2n的每个位置组长都是自己 for(int i = 1; i <= n * 2; i++) fa[i] = i; // 处理m个关系 while(m--) { char op; // 关系类型：F（朋友）/E（敌人） int x, y; // 有关系的两个人 cin >> op >> x >> y; if(op == 'F') // 朋友关系：合并x和y的原域 { un(x, y); } else // 敌人关系：合并x和y的敌域、y和x的敌域 { un(x, y + n); // x 加入 y的敌域 un(y, x + n); // y 加入 x的敌域 } } // 统计团体数：原域（1~n）中组长是自己的数量 int ret = 0; for(int i = 1; i <= n; i++) { if(fa[i] == i) ret++; } cout << ret << endl; // 输出团体数 return 0; }

1.6.2⻝物链

题目描述

动物王国中有三类动物 A,B,C，这三类动物的食物链构成了有趣的环形。A 吃 B，B 吃 C，C 吃 A。

现有 N 个动物，以 1∼N 编号。每个动物都是 A,B,C 中的一种，但是我们并不知道它到底是哪一种。

有人用两种说法对这 N 个动物所构成的食物链关系进行描述：

• 第一种说法是1 X Y，表示 X 和 Y 是同类。
• 第二种说法是2 X Y，表示 X 吃 Y。

此人对 N 个动物，用上述两种说法，一句接一句地说出 K 句话，这 K 句话有的是真的，有的是假的。当一句话满足下列三条之一时，这句话就是假话，否则就是真话。

• 当前的话与前面的某些真的话冲突，就是假话；
• 当前的话中 X 或 Y 比 N 大，就是假话；
• 当前的话表示 X 吃 X，就是假话。

你的任务是根据给定的 N 和 K 句话，输出假话的总数。

输入格式

第一行两个整数，N,K，表示有 N 个动物，K 句话。

第二行开始每行一句话。格式见题目描述与样例。

输出格式

一行，一个整数，表示假话的总数。

输入输出样例

输入 #1复制

100 7 1 101 1 2 1 2 2 2 3 2 3 3 1 1 3 2 3 1 1 5 5

输出 #1复制

3

说明/提示

对于全部数据，1≤N≤5×104，1≤K≤105。

【解法】

【参考代码】

#include <iostream> using namespace std; const int N = 5e4 + 10; // 动物最多5万，三倍扩展后15万+10 int n, k; // n=动物数，k=话的数量 int fa[N * 3]; // 三倍扩展域并查集：1~n(同类)、n+1~2n(捕食)、2n+1~3n(被捕食) // find函数：找x的最终组长（路径压缩，提速） int find(int x) { return x == fa[x] ? x : fa[x] = find(fa[x]); } // un函数：合并x和y的集合（让x的组长指向y的组长） void un(int x, int y) { fa[find(x)] = find(y); } int main() { cin >> n >> k; // 初始化扩展域并查集：1~3n的每个位置组长都是自己 for(int i = 1; i <= n * 3; i++) fa[i] = i; int ret = 0; // 统计假话数量，初始为0 // 处理k句话 while(k--) { int op, x, y; cin >> op >> x >> y; // 假话条件2：X或Y超过n → 直接记假话 if(x > n || y > n) { ret++; continue; // 跳过后续判断 } if(op == 1) // 第1种说法：X和Y是同类 { // 冲突判定：X在Y的捕食域（find(x)==find(y+n)）或被捕食域（find(x)==find(y+2n)） if(find(x) == find(y + n) || find(x) == find(y + 2 * n)) { ret++; // 假话，计数+1 } else { // 合并同类域、捕食域、被捕食域 un(x, y); // 同类域合并 un(x + n, y + n); // 捕食域合并 un(x + 2 * n, y + 2 * n); // 被捕食域合并 } } else // 第2种说法：X吃Y { // 冲突判定：X和Y是同类（find(x)==find(y)），或X在Y的捕食域（Y吃X，冲突） if(find(x) == find(y) || find(x) == find(y + n)) { ret++; // 假话，计数+1 } else { // 合并规则：X吃Y → 维护三种关系 un(x, y + 2 * n); // X的同类域 ↔ Y的被捕食域 un(y, x + n); // Y的同类域 ↔ X的捕食域 un(x + 2 * n, y + n); // X的被捕食域 ↔ Y的捕食域 } } } cout << ret << endl; // 输出假话总数 return 0; }

1.7带权并查集

1.带权并查集的概念

2.带权并查集的实现

初始化init：

const int N = 1e5 + 10, INF = 0x3f3f3f3f; int n; int fa[N], d[N]; void init() { for(int i = 1; i <= n; i++) { fa[i] = i; d[i] = 0; // 根据题⽬要求来初始化 } }

查询根节点操作find：

int find(int x) { if(fa[x] == x) return x; int t = find(fa[x]); // 这句代码⼀定要先执⾏，先让⽗结点挂在根节点的后⾯ d[x] += d[fa[x]]; // 注意，可能会根据权值的意义有所改变 return fa[x] = t; }

合并操作union：

// x 所在集合与 y 所在集合合并，x 与 y 之间的权值是 w void un(int x, int y, int w) { int fx = find(x), fy = find(y); if(fx != fy) // 不在同⼀个集合中 { fa[fx] = fy; d[fx] = d[y] + w - d[x]; // 注意，可能会根据权值的意义有所改变 } }

查询距离操作query：

// 查询 x 到 y 的距离 int query(int x, int y) { int fx = find(x), fy = find(y); if(fx != fy) return INF; // 如果不在同⼀个集合中，说明距离未知 return d[y] - d[x]; }

1.7.1⻝物链

题目描述

动物王国中有三类动物 A,B,C，这三类动物的食物链构成了有趣的环形。A 吃 B，B 吃 C，C 吃 A。

现有 N 个动物，以 1∼N 编号。每个动物都是 A,B,C 中的一种，但是我们并不知道它到底是哪一种。

有人用两种说法对这 N 个动物所构成的食物链关系进行描述：

• 第一种说法是1 X Y，表示 X 和 Y 是同类。
• 第二种说法是2 X Y，表示 X 吃 Y。

此人对 N 个动物，用上述两种说法，一句接一句地说出 K 句话，这 K 句话有的是真的，有的是假的。当一句话满足下列三条之一时，这句话就是假话，否则就是真话。

• 当前的话与前面的某些真的话冲突，就是假话；
• 当前的话中 X 或 Y 比 N 大，就是假话；
• 当前的话表示 X 吃 X，就是假话。

你的任务是根据给定的 N 和 K 句话，输出假话的总数。

输入格式

第一行两个整数，N,K，表示有 N 个动物，K 句话。

第二行开始每行一句话。格式见题目描述与样例。

输出格式

一行，一个整数，表示假话的总数。

输入输出样例

输入 #1复制

100 7 1 101 1 2 1 2 2 2 3 2 3 3 1 1 3 2 3 1 1 5 5

输出 #1复制

3

说明/提示

对于全部数据，1≤N≤5×104，1≤K≤105。

【解法】

【参考代码】

#include <iostream> using namespace std; const int N = 5e4 + 10; // 动物最多5万，足够存储 int n, k; // n=动物数，k=话的数量 int fa[N], d[N]; // fa[]：父节点；d[]：当前节点到根节点的权值（距离） // find函数：找x的根节点，同时更新d[x]（路径压缩+权值更新） int find(int x) { if(fa[x] == x) return x; // x是根节点，直接返回 int t = find(fa[x]); // 先找父节点的根（递归） d[x] += d[fa[x]]; // 更新x到根的权值：x→父节点 + 父节点→根 return fa[x] = t; // 路径压缩：x直接指向根 } // un函数：合并x和y的集合，w是x和y的期望权值（0=同类，2=x吃y） void un(int x, int y, int w) { int fx = find(x), fy = find(y); // 找x和y的根 if(fx != fy) // 不在同一集合，需要合并 { fa[fx] = fy; // 把x的根挂到y的根上 // 核心：更新fx到fy的权值，保证(d[y]-d[x])%3 = w d[fx] = d[y] + w - d[x]; } } int main() { cin >> n >> k; // 初始化：每个动物的父节点是自己，权值为0（到自己的距离为0） for(int i = 1; i <= n; i++) fa[i] = i; int ret = 0; // 统计假话数量 while(k--) { int op, x, y; cin >> op >> x >> y; // 先处理边界：X/Y超出范围 → 假话 if(x > n || y > n) { ret++; continue; } // 提前找根（后续判断冲突需要） int fx = find(x), fy = find(y); if(op == 1) // 说法1：X和Y是同类（期望(d[y]-d[x])%3=0） { // 冲突条件：同集合，但权值差模3≠0 if(fx == fy && ((d[y] - d[x]) % 3 + 3) % 3 != 0) { ret++; } else { un(x, y, 0); // 合并，期望权值0（同类） } } else // 说法2：X吃Y（期望(d[y]-d[x])%3=2 → 对应x吃y） { // 特殊情况：X=Y（X吃X）→ 假话 if(x == y) { ret++; continue; } // 冲突条件：同集合，但权值差模3≠1（注意：代码里写的是≠1，等价于≠2，看推导） if(fx == fy && ((d[y] - d[x]) % 3 + 3) % 3 != 1) { ret++; } else { un(x, y, 2); // 合并，期望权值2（X吃Y） } } } cout << ret << endl; return 0; }

1.7.2银河英雄传说

题目背景

公元 5801 年，地球居民迁至金牛座 α 第二行星，在那里发表银河联邦创立宣言，同年改元为宇宙历元年，并开始向银河系深处拓展。

宇宙历 799 年，银河系的两大军事集团在巴米利恩星域爆发战争。泰山压顶集团派宇宙舰队司令莱因哈特率领十万余艘战舰出征，气吞山河集团点名将杨威利组织麾下三万艘战舰迎敌。

题目描述

杨威利擅长排兵布阵，巧妙运用各种战术屡次以少胜多，难免恣生骄气。在这次决战中，他将巴米利恩星域战场划分成 30000 列，每列依次编号为 1,2,…,30000。之后，他把自己的战舰也依次编号为 1,2,…,30000，让第 i 号战舰处于第 i 列，形成“一字长蛇阵”，诱敌深入。这是初始阵形。当进犯之敌到达时，杨威利会多次发布合并指令，将大部分战舰集中在某几列上，实施密集攻击。合并指令为M i j，含义为第 i 号战舰所在的整个战舰队列，作为一个整体（头在前尾在后）接至第 j 号战舰所在的战舰队列的尾部。显然战舰队列是由处于同一列的一个或多个战舰组成的。合并指令的执行结果会使队列增大。

然而，老谋深算的莱因哈特早已在战略上取得了主动。在交战中，他可以通过庞大的情报网络随时监听杨威利的舰队调动指令。

在杨威利发布指令调动舰队的同时，莱因哈特为了及时了解当前杨威利的战舰分布情况，也会发出一些询问指令：C i j。该指令意思是，询问电脑，杨威利的第 i 号战舰与第 j 号战舰当前是否在同一列中，如果在同一列中，那么它们之间布置有多少战舰。

作为一个资深的高级程序设计员，你被要求编写程序分析杨威利的指令，以及回答莱因哈特的询问。

最终的决战已经展开，银河的历史又翻过了一页……

输入格式

第一行有一个整数 T（1≤T≤5×105），表示总共有 T 条指令。

以下有 T 行，每行有一条指令。指令有两种格式：

1. M i j：i 和 j 是两个整数（1≤i,j≤30000），表示指令涉及的战舰编号。该指令是莱因哈特窃听到的杨威利发布的舰队调动指令，并且保证第 i 号战舰与第 j 号战舰不在同一列。

2. C i j：i 和 j 是两个整数（1≤i,j≤30000），表示指令涉及的战舰编号。该指令是莱因哈特发布的询问指令。

每条指令中都保证 i=j。

输出格式

依次对输入的每一条指令进行分析和处理：

• 如果是杨威利发布的舰队调动指令，则表示舰队排列发生了变化，你的程序要注意到这一点，但是不要输出任何信息。
• 如果是莱因哈特发布的询问指令，你的程序要输出一行，仅包含一个整数，表示在同一列上，第 i 号战舰与第 j 号战舰之间布置的战舰数目。如果第 i 号战舰与第 j 号战舰当前不在同一列上，则输出 −1。

输入输出样例

输入 #1复制

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

输出 #1复制

-1 1

说明/提示

样例解释

战舰位置图：表格中阿拉伯数字表示战舰编号。

【解法】

【参考代码】

#include <iostream> #include <cstdlib> // 用于abs函数（绝对值） using namespace std; const int N = 3e4 + 10; // 战舰最多3万，留10余量 int n = 3e4; // 固定战舰总数30000 int fa[N], d[N], cnt[N]; // fa=父节点，d=到父节点的距离，cnt=集合大小（列战舰数） // find函数：找x的根节点，同时更新d[x]（路径压缩+权值更新） int find(int x) { if(fa[x] == x) return x; // x是根节点，直接返回 int t = find(fa[x]); // 递归找父节点的根 d[x] += d[fa[x]]; // 更新x到根的距离：x→父 + 父→根 return fa[x] = t; // 路径压缩：x直接指向根 } // un函数：合并x所在列到y所在列的尾部 void un(int x, int y) { int fx = find(x), fy = find(y); // 找x和y的根 if(fx != fy) // 不在同一列，执行合并 { fa[fx] = fy; // 把x的根挂到y的根上 d[fx] = cnt[fy]; // fx到fy的距离 = y列的总战舰数 cnt[fy] += cnt[fx]; // 合并后y列总数 = 原y列数 + 原x列数 } } // query函数：查询x和y之间的战舰数 int query(int x, int y) { int fx = find(x), fy = find(y); // 找x和y的根 if(fx != fy) return -1; // 根不同→不在同一列 // 根相同→距离差的绝对值减1（中间的战舰数） return abs(d[x] - d[y]) - 1; } int main() { // 初始化：每个战舰的父节点是自己，距离为0，列数为1 for(int i = 1; i <= n; i++) { fa[i] = i; // 初始父节点是自己 d[i] = 0; // 初始到自己的距离为0 cnt[i] = 1; // 初始每列只有1艘战舰 } int T; cin >> T; // 读入指令总数 while(T--) { char op; int x, y; cin >> op >> x >> y; // 读入指令类型和战舰编号 if(op == 'M') // 合并指令：x列接在y列尾部 { un(x, y); } else // 查询指令：C x y { cout << query(x, y) << endl; } } return 0; }