带权并查集实战：2001年NOI食物链问题详解

胡志明t

一、问题背景与算法思路

食物链问题需要维护三种生物关系（同类、捕食、被捕食），判断K条陈述中有多少是假话。这个问题**展现了带权并查集在关系维护中的强大能力。

二、完整代码实现（带详细注释）

1. #include <iostream>
   
2. #include <vector>
   
3. using namespACe std;
   
4. 
   
5. const int MAXN = 50010;
   
6. 
   
7. class UnionFind {
   
8. private:
   
9.     vector<int> parent;   // 父节点数组
   
10.     vector<int> rank;     // 秩数组
    
11.     vector<int> relation; // 关系数组：0-同类 1-吃父节点 2-被父节点吃
    
12.    
    
13. public:
    
14.     // 构造函数：初始化并查集
    
15.     UnionFind(int n) : parent(n+1), rank(n+1, 0), relation(n+1, 0) {
    
16.         for(int i = 0; i <= n; ++i) {
    
17.             parent[i] = i; // 初始时每个元素的父节点是自己
    
18.         }
    
19.     }
    
20.    
    
21.     // 查找根节点（带路径压缩和关系维护）
    
22.     int find(int x) {
    
23.         if(parent[x] != x) {
    
24.             int orig_parent = parent[x];
    
25.             parent[x] = find(parent[x]); // 路径压缩
    
26.             relation[x] = (relation[x] + relation[orig_parent]) % 3; // 更新关系
    
27.         }
    
28.         return parent[x];
    
29.     }
    
30.    
    
31.     // 合并**（带关系维护）
    
32.     bool unite(int x, int y, int type) {
    
33.         int rootX = find(x);
    
34.         int rootY = find(y);
    
35.         
    
36.         if(rootX == rootY) { // 已在同一**
    
37.             // 检查关系是否矛盾
    
38.             if((relation[x] - relation[y] + 3) % 3 != type)
    
39.                 return false;
    
40.             return true;
    
41.         }
    
42.         
    
43.         // 按秩合并（小树合并到大树）
    
44.         if(rank[rootX] > rank[rootY]) {
    
45.             parent[rootY] = rootX;
    
46.             relation[rootY] = (relation[x] - relation[y] - type + 6) % 3;
    
47.         } else {
    
48.             parent[rootX] = rootY;
    
49.             relation[rootX] = (relation[y] - relation[x] + type + 3) % 3;
    
50.             if(rank[rootX] == rank[rootY]) {
    
51.                 rank[rootY]++; // 秩相同时合并后秩+1
    
52.             }
    
53.         }
    
54.         return true;
    
55.     }
    
56. };
    
57. 
    
58. int main() {
    
59.     ios::sync_with_stdio(false);
    
60.     cin.tie(nullptr);
    
61.    
    
62.     int N, K;
    
63.     cin >> N >> K;
    
64.    
    
65.     UnionFind uf(N);
    
66.     int falseCount = 0;
    
67.    
    
68.     for(int i = 0; i < K; ++i) {
    
69.         int type, x, y;
    
70.         cin >> type >> x >> y;
    
71.         
    
72.         // 输入合法性检查
    
73.         if(x > N || y > N || (type == 2 && x == y)) {
    
74.             falseCount++;
    
75.             continue;
    
76.         }
    
77.         
    
78.         // 关系类型转换：1->0(同类), 2->1(捕食)
    
79.         int rel = type - 1;
    
80.         
    
81.         if(!uf.unite(x, y, rel)) {
    
82.             falseCount++;
    
83.         }
    
84.     }
    
85.    
    
86.     cout << falseCount << endl;
    
87.     return 0;
    
88. }

复制代码

三、关键算法要点

• 关系维护技巧：通过模3运算维护三种关系
• 路径压缩优化：在find操作中同时更新关系
• 按秩合并策略：保持树结构的平衡性
• 关系验证机制：合并时检查关系是否矛盾
  
  

四、复杂度分析

• 时间复杂度：O(Kα(N))，其中α是反阿克曼函数
• 空间复杂度：O(N)
  
  

五、常见错误提醒

• 忘记处理自相矛盾的情况（X吃X）
• 关系更新公式错误
• 输入范围检查遗漏
• 模运算处理不当
  
  

六、学习价值

通过本题可以掌握：

• 带权并查集的设计思想
• 关系传递性的数学建模
• 路径压缩与按秩合并的协同工作
• 复杂关系的维护技巧
  
  

来源：带权并查集实战：2001年NOI食物链问题详解