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

一、问题背景与算法思路

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

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

#include <iostream>
#include <vector>
using namespACe std;

const int MAXN = 50010;

class UnionFind {
private:
    vector<int> parent;   // 父节点数组
    vector<int> rank;     // 秩数组
    vector<int> relation; // 关系数组：0-同类 1-吃父节点 2-被父节点吃
    
public:
    // 构造函数：初始化并查集
    UnionFind(int n) : parent(n+1), rank(n+1, 0), relation(n+1, 0) {
        for(int i = 0; i <= n; ++i) {
            parent[i] = i; // 初始时每个元素的父节点是自己
        }
    }
    
    // 查找根节点（带路径压缩和关系维护）
    int find(int x) {
        if(parent[x] != x) {
            int orig_parent = parent[x];
            parent[x] = find(parent[x]); // 路径压缩
            relation[x] = (relation[x] + relation[orig_parent]) % 3; // 更新关系
        }
        return parent[x];
    }
    
    // 合并集合（带关系维护）
    bool unite(int x, int y, int type) {
        int rootX = find(x);
        int rootY = find(y);
        
        if(rootX == rootY) { // 已在同一集合
            // 检查关系是否矛盾
            if((relation[x] - relation[y] + 3) % 3 != type)
                return false;
            return true;
        }
        
        // 按秩合并（小树合并到大树）
        if(rank[rootX] > rank[rootY]) {
            parent[rootY] = rootX;
            relation[rootY] = (relation[x] - relation[y] - type + 6) % 3;
        } else {
            parent[rootX] = rootY;
            relation[rootX] = (relation[y] - relation[x] + type + 3) % 3;
            if(rank[rootX] == rank[rootY]) {
                rank[rootY]++; // 秩相同时合并后秩+1
            }
        }
        return true;
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int N, K;
    cin >> N >> K;
    
    UnionFind uf(N);
    int falseCount = 0;
    
    for(int i = 0; i < K; ++i) {
        int type, x, y;
        cin >> type >> x >> y;
        
        // 输入合法性检查
        if(x > N || y > N || (type == 2 && x == y)) {
            falseCount++;
            continue;
        }
        
        // 关系类型转换：1->0(同类), 2->1(捕食)
        int rel = type - 1;
        
        if(!uf.unite(x, y, rel)) {
            falseCount++;
        }
    }
    
    cout << falseCount << endl;
    return 0;
}

三、关键算法要点

1. 关系维护技巧：通过模3运算维护三种关系

2. 路径压缩优化：在find操作中同时更新关系

3. 按秩合并策略：保持树结构的平衡性

4. 关系验证机制：合并时检查关系是否矛盾

四、复杂度分析

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

• 空间复杂度：O(N)

五、常见错误提醒

1. 忘记处理自相矛盾的情况（X吃X）

2. 关系更新公式错误

3. 输入范围检查遗漏

4. 模运算处理不当

六、学习价值

通过本题可以掌握：

• 带权并查集的设计思想

• 关系传递性的数学建模

• 路径压缩与按秩合并的协同工作

• 复杂关系的维护技巧