[NOI2001] 食物链题解

思路

给每只动物赋一个模 $3$ 的类别编号，并约定 $type_x-type_y\equiv1\pmod3$ 表示 $x$ 吃 $y$。于是同类陈述要求差为 $0$，捕食陈述要求差为 $1$。

使用带权并查集。令 $dis_x$ 表示 $type_x-type_{parent_x}$ 模 $3$ 的值。路径压缩时同步累加权值，从而在找到根后得到 $type_x-type_{root_x}$。

若 $x,y$ 已在同一集合，只需检查当前差是否等于陈述要求；不相等则是假话。若根不同，则按该陈述确定两个根之间的权值并合并。越界和自己吃自己在进入并查集前直接计为假话。

做法

1. 初始化每只动物为独立集合，权值为零。
2. 依次读取陈述，先检查编号范围和自己吃自己的情况。
3. 对合法编号执行带权查找；同根时校验模 $3$ 差值，异根时按陈述合并。
4. 只有真话会更新并查集，最终输出假话计数。

正确性证明

并查集权值始终表示节点类别与父节点类别之差。路径压缩把沿途差值相加，因此查找后 $dis_x$ 等于 $type_x-type_{root_x}$。

当两个节点同根时，它们的类别差已经由此前真话唯一确定为 $dis_x-dis_y$。当前陈述要求的差若与之不同，就与此前真话冲突；若相同则一致。当根不同时，两个集合间尚无约束，按当前陈述设置根间差值即可使该陈述成立，并保持两个集合内部所有旧关系不变。因此算法恰好接受所有可与此前真话共同成立的陈述，拒绝的正是假话。

复杂度

时间复杂度为 $O((N+K)\alpha(N))$，空间复杂度为 $O(N)$。