扩展域并查集 带权并查集
[NOI2001] 食物链
题目描述
动物王国中有三类动物 A , B , C A,B,C A,B,C，这三类动物的食物链构成了有趣的环形。 A A A 吃 B B B， B B B 吃 C C C， C C C 吃 A A A。
现有 N N N 个动物，以 1 ∼ N 1 \sim N 1∼N 编号。每个动物都是 A , B , C A,B,C A,B,C 中的一种，但是我们并不知道它到底是哪一种。
有人用两种说法对这 N N N 个动物所构成的食物链关系进行描述：
- 第一种说法是
1 X Y，表示 X X X 和 Y Y Y 是同类。 - 第二种说法是
2 X Y，表示 X X X 吃 Y Y Y。
此人对 N N N 个动物，用上述两种说法，一句接一句地说出 K K K 句话，这 K K K 句话有的是真的，有的是假的。当一句话满足下列三条之一时，这句话就是假话，否则就是真话。
- 当前的话与前面的某些真的话冲突，就是假话；
- 当前的话中 X X X 或 Y Y Y 比 N N N 大，就是假话；
- 当前的话表示 X X X 吃 X X X，就是假话。
你的任务是根据给定的 N N N 和 K K K 句话，输出假话的总数。
输入格式
第一行两个整数， N , K N,K N,K，表示有 N N N 个动物， K K K 句话。
第二行开始每行一句话（按照题目要求，见样例）
输出格式
一行，一个整数，表示假话的总数。
样例 #1
样例输入 #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 × 1 0 4 1\le N\le 5 \times 10^4 1≤N≤5×104， 1 ≤ K ≤ 1 0 5 1\le K \le 10^5 1≤K≤105。
题解
扩展域并查集详解
扩展域并查集是一种通过将每个元素拆分成多个域（或状态）来表示复杂关系的并查集方法。在食物链问题中，我们需要处理动物之间的同类关系和捕食关系，扩展域并查集通过将每个动物拆分成多个域来表示其可能的类别（如 A、B、C），从而高效地处理这些关系。
核心思想
-
拆分域：
- 每个动物
x拆分成三个域：x：表示动物x属于A类。x + n：表示动物x属于B类。x + 2n：表示动物x属于C类。
- 这里的
n是动物的总数，确保每个域的唯一性。
- 每个动物
-
关系表示：
- 这里我们结合题意 A − > B − > C − > A A->B->C->A A−>B−>C−>A的食物链，进行分析如下：
- 如果动物
x和y是同类，那么它们的A、B、C域分别属于同一集合。因为题目中只有 A B C ABC ABC三个物种，同类的下一级物种不会互相吃，同类的天敌也不会互相吃，所以合并的时候需要把猎物和天敌一并更新。 - 如果动物
x吃y，那么：x的A域和y的C域属于同一集合。unity(x, y + 2 * n);//x的同类是y的天敌x的B域和y的A域属于同一集合。unity(x + n, y);//x的猎物是y的同类x的C域和y的B域属于同一集合。这里可以在食物链里模拟一下就能理解。unity(x + 2 * n, y + n);//x的天敌是y的猎物
-
矛盾检测：
- 如果当前说法与已维护的关系矛盾，则判断为假话。即同类不能与捕食关系共存。
具体步骤
1. 初始化
- 初始化并查集，每个域独立成集合。
for (int i = 1; i <= 3 * n; i++) { p[i] = i; }
2. 处理说法
- 对于每种说法，检查是否与已维护的关系矛盾：
- 说法 1：
x和y是同类。- 检查
x的A域是否与y的B或C域在同一集合。即没有捕食关系 - 如果没有矛盾，合并
x和y的A、B、C域。
- 检查
- 说法 2：
x吃y。- 检查
x的A域是否与y的A或C域在同一集合。即没有同类关系或者反向捕食关系。 - 如果没有矛盾，合并
x的A域与y的B域，x的B域与y的C域，x的C域与y的A域。
- 检查
- 说法 1：
3. 假话统计
- 如果说法与已维护的关系矛盾，则统计为假话。
代码实现
#include <iostream>
#include <vector>
using namespace std;
const int MAXN = 50010;
int p[MAXN * 3]; // 扩展域并查集，每个动物拆分为3个域
// 查找函数，带路径压缩
int find(int x) {
if (p[x] != x) {
p[x] = find(p[x]);
}
return p[x];
}
// 合并函数
void merge(int x, int y) {
p[find(x)] = find(y);
}
int main() {
int n, k;
cin >> n >> k;
// 初始化扩展域并查集
for (int i = 1; i <= 3 * n; i++) {
p[i] = i;
}
int ans = 0; // 假话数量
while (k--) {
int t, x, y;
cin >> t >> x >> y;
// 越界或自吃，直接判断为假话
if (x > n || y > n) {
ans++;
continue;
}
if (t == 2 && x == y) {
ans++;
continue;
}
if (t == 1) {
// x和y是同类
if (find(x) == find(y + n) || find(x) == find(y + 2 * n)) {
ans++; // 矛盾
} else {
// 合并x和y的同类域
merge(x, y);
merge(x + n, y + n);
merge(x + 2 * n, y + 2 * n);
}
} else {
// x吃y
if (find(x) == find(y) || find(x) == find(y + 2 * n)) {
ans++; // 矛盾
} else {
// 合并x的A域和y的B域，x的B域和y的C域，x的C域和y的A域
merge(x, y + n);
merge(x + n, y + 2 * n);
merge(x + 2 * n, y);
}
}
}
cout << ans << endl;
return 0;
}
示例分析
输入
100 7
1 101 1
2 1 2
2 2 3
2 3 3
1 1 3
2 3 1
1 5 5
处理过程
- 说法
1 101 1：101越界，假话。 - 说法
2 1 2：1吃2，合并1的A域与2的B域，1的B域与2的C域，1的C域与2的A域。 - 说法
2 2 3：2吃3，合并2的A域与3的B域，2的B域与3的C域，2的C域与3的A域。 - 说法
2 3 3：3吃3，自吃，假话。 - 说法
1 1 3：1和3是同类，检查是否矛盾。如果1的A域与3的B或C域在同一集合，则矛盾。 - 说法
2 3 1：3吃1，检查是否矛盾。如果3的A域与1的A或C域在同一集合，则矛盾。 - 说法
1 5 5：5和5是同类，合法。
输出
3
总结
扩展域并查集通过拆分域来表示复杂关系，逻辑直观且易于理解。虽然空间开销较大，但在处理复杂关系问题时非常高效。
带权并查集详解
带权并查集是一种在普通并查集的基础上，为每个节点维护一个权值（或关系）的数据结构。通过权值，我们可以表示节点之间的复杂关系（如捕食关系、同类关系等）。在食物链问题中，带权并查集通过权值来表示动物之间的捕食关系，从而高效地判断给定的说法是否为假话。
核心思想
思想是没有合并到一起的集合不会产生矛盾。被合并的集合，有相同的集合代表，根据该点和集合代表点的关系推断。
-
权值定义：
- 每个节点
x维护一个权值d[x]，表示x与其父节点p[x]的关系。 - 权值的具体含义：
d[x] = 0：x和p[x]是同类。d[x] = 1：x吃p[x]。d[x] = 2：x被p[x]吃。
- 每个节点
-
路径压缩：
- 在查找根节点的过程中，路径压缩会将每个节点的父节点直接指向根节点，并更新权值
d[x]，确保权值表示的是x到根节点的总关系。
- 在查找根节点的过程中，路径压缩会将每个节点的父节点直接指向根节点，并更新权值
-
关系推导：
- 通过权值的模运算，可以推导出任意两个节点之间的关系。
- 例如：
- 如果
d[x] = 1，d[y] = 0，则x吃y。 - 如果
d[x] = 2，d[y] = 1，则x吃y。
- 如果
-
合并操作：
- 当合并两个集合时，根据当前说法调整权值，确保合并后的关系正确。
具体步骤
1. 初始化
- 初始化并查集，每个节点的父节点为自身，权值为
0。for (int i = 1; i <= n; i++) { p[i] = i; d[i] = 0; }
2. 查找函数
- 查找节点
x的根节点，并在路径压缩的过程中更新权值。int find(int x) { if (p[x] != x) { int orig_p = p[x]; // 保存原始父节点 p[x] = find(p[x]); // 递归找到根节点 d[x] = (d[x] + d[orig_p]) % 3; // 更新权值 } return p[x]; }
3. 处理说法
- 对于每种说法，检查是否与已维护的关系矛盾：
- 说法 1：
x和y是同类。- 找到
x和y的根节点rx和ry。 - 如果
rx == ry，检查d[x]和d[y]是否相等。 - 如果
rx != ry，合并两个集合，并调整权值。
- 找到
- 说法 2：
x吃y。- 找到
x和y的根节点rx和ry。 - 如果
rx == ry，检查(d[x] - d[y] + 3) % 3是否等于1。 - 如果
rx != ry，合并两个集合，并调整权值。
- 找到
- 说法 1：
4. 假话统计
- 如果说法与已维护的关系矛盾，则统计为假话。
代码实现
#include <iostream>
#include <vector>
using namespace std;
const int MAXN = 50010;
int p[MAXN]; // 父节点数组
int d[MAXN]; // 权值数组，表示与父节点的关系
// 查找函数，带路径压缩和权值更新
int find(int x) {
if (p[x] != x) {
int orig_p = p[x]; // 保存原始父节点
p[x] = find(p[x]); // 递归找到根节点
d[x] = (d[x] + d[orig_p]) % 3; // 更新权值
}
return p[x];
}
int main() {
int n, k;
cin >> n >> k;
// 初始化并查集
for (int i = 1; i <= n; i++) {
p[i] = i;
d[i] = 0;
}
int ans = 0; // 假话数量
while (k--) {
int t, x, y;
cin >> t >> x >> y;
// 越界或自吃，直接判断为假话
if (x > n || y > n) {
ans++;
continue;
}
if (t == 2 && x == y) {
ans++;
continue;
}
int rx = find(x), ry = find(y); // 找到x和y的根节点
if (rx != ry) {
// 合并两个集合
p[rx] = ry;
if (t == 1) {
d[rx] = (d[y] - d[x] + 3) % 3; // x和y是同类
} else {
d[rx] = (d[y] - d[x] + 4) % 3; // x吃y
}
} else {
// 同一集合内，检查关系是否矛盾
if (t == 1 && (d[x] - d[y] + 3) % 3 != 0) {
ans++;
} else if (t == 2 && (d[x] - d[y] + 3) % 3 != 1) {
ans++;
}
}
}
cout << ans << endl;
return 0;
}
示例分析
输入
100 7
1 101 1
2 1 2
2 2 3
2 3 3
1 1 3
2 3 1
1 5 5
处理过程
- 说法
1 101 1：101越界，假话。 - 说法
2 1 2：1吃2，合并1和2的集合，调整权值。 - 说法
2 2 3：2吃3，合并2和3的集合，调整权值。 - 说法
2 3 3：3吃3，自吃，假话。 - 说法
1 1 3：1和3是同类，检查是否矛盾。 - 说法
2 3 1：3吃1，检查是否矛盾。 - 说法
1 5 5：5和5是同类，合法。
输出
3
总结
带权并查集通过维护权值来表示节点之间的关系，路径压缩和权值更新确保了高效的关系推导。虽然逻辑稍复杂，但代码简洁且高效，适合处理类似食物链的问题。