基于带权并查集的食物链关系判定
题目来源：POJ 1182
问题描述：
在一片虚拟的动物世界中，存在三类生物 A、B 和 C，它们构成一个循环捕食系统：A 捕食 B，B 捕食 C，C 捕食 A。现有 N 只编号为 1 到 N 的动物，每只属于其中一类，但具体类别未知。接下来会给出 K 条语句，每条语句描述两个个体之间的关系，形式如下：
- 类型 1：X 与 Y 是同类。
- 类型 2：X 捕食 Y。
这些语句可能为真也可能为假。若某句话满足以下任一条件，则视为假话：
- 与之前已确认为真的陈述矛盾；
- X 或 Y 超出合法范围 [1, N]；
- 声称某个个体捕食自己（即 X 吃 X）。
目标是统计所有被判定为假话的语句总数。
输入格式：
首行包含两个整数 N 和 K，分别表示动物数量和语句条数。随后 K 行，每行三个整数 D、X、Y，D 表示语句类型（1 或 2），X 和 Y 为涉及的动物编号。
输出格式：
输出一个整数，代表假话的总数量。
样例输入：
100 7
1 101 1
2 1 2
2 2 3
2 3 3
1 1 3
2 3 1
1 5 5
样例输出：
3
解法思路：
采用扩展并查集结构来维护动物间的相对关系。核心思想是将每个节点 x 拆分为三个角色：
- x 表示其本身；
- x + N 表示它的天敌（捕食者）；
- x + 2*N 表示它的猎物（被它捕食的对象）。
通过这种方式，可以利用并查集维护这三种状态之间的等价类。例如：
- 当 X 与 Y 是同类时，应合并 (x, y)、(x+N, y+N)、(x+2N, y+2N)，以保持角色一致性；
- 当 X 捕食 Y 时，说明 X 是 Y 的捕食者的同类，因此需要合并 (x, y+N)，同时推导出其他对应关系：x 的猎物（x+2N）应等于 y（y 本身为其猎物的猎物），x+N 应连接到 y+2N。
在处理每条语句前，先判断是否违反基本规则（越界或自食）。然后根据当前语句类型检查是否存在冲突——即是否已有路径表明其不可能成立。如果没有冲突，则执行相应的合并操作；否则计数器加一。
实现代码如下：
#include <cstdio>
const int MAX_SIZE = 50005;
int parent[3 * MAX_SIZE];
int rank[3 * MAX_SIZE];
// 初始化并查集
void initialize(int size) {
for (int i = 0; i < size; ++i) {
parent[i] = i;
rank[i] = 0;
}
}
// 查找根节点（带路径压缩）
int findRoot(int node) {
if (parent[node] != node)
parent[node] = findRoot(parent[node]);
return parent[node];
}
// 合并两个集合（按秩合并）
void mergeSets(int u, int v) {
int rootU = findRoot(u);
int rootV = findRoot(v);
if (rootU == rootV) return;
if (rank[rootU] < rank[rootV]) {
parent[rootU] = rootV;
} else {
parent[rootV] = rootU;
if (rank[rootU] == rank[rootV])
rank[rootU]++;
}
}
// 判断两节点是否在同一集合
bool isConnected(int a, int b) {
return findRoot(a) == findRoot(b);
}
int main() {
int n, k;
scanf("%d %d", &n, &k);
initialize(3 * n);
int falseCount = 0;
for (int i = 0; i < k; ++i) {
int type, x, y;
scanf("%d %d %d", &type, &x, &y);
// 编号转为0基索引
--x; --y;
// 检查是否越界
if (x < 0 || x >= n || y < 0 || y >= n) {
falseCount++;
continue;
}
if (type == 1) { // 同类关系
if (isConnected(x, y + n) || isConnected(x, y + 2 * n)) {
falseCount++;
} else {
mergeSets(x, y);
mergeSets(x + n, y + n);
mergeSets(x + 2 * n, y + 2 * n);
}
} else { // 捕食关系
if (x == y || isConnected(x, y) || isConnected(x, y + 2 * n)) {
falseCount++;
} else {
mergeSets(x, y + n);
mergeSets(x + n, y + 2 * n);
mergeSets(x + 2 * n, y);
}
}
}
printf("%d\n", falseCount);
return 0;
}
