P2024食物链题解中，如何运用并查集解决洛谷NOI2001问题？
- 内容介绍
- 文章标签
- 相关推荐
本文共计499个文字，预计阅读时间需要2分钟。
题目链接：https://www.luogu.com.cn/problem/P2024解题思路：我们用 $X+n$ 来表示吃 $X$ 的集合，用 $X+2n$ 来表示被 $X$ 吃的集合，同时可以推导出 $X$ 的值。题目链接：https://www.luogu.com.cn/problem/P2024 解题思路：我们用吃来表示集合，用被吃来表示另一个集合，通过这种关系可以推导出 $X$ 的值。
解题思路：我们用 \(X+n\) 来表示 吃 \(X\) 的集合，用 \(X+2n\) 来表示被 \(X\) 吃的集合，同时可以推导出 \(X+2n\) 是吃 \(X+n\) 的。
遇到“1 X Y”，则说明需要：
- 合并 \(X\) 和 \(Y\)；
- 合并 \(X+n\) 和 \(Y+n\)；
- 合并 \(X+2n\) 和 \(Y+2n\)。
但是在此之前需要先判断：如果 \(X\) 和 \(Y+n\) 或者 \(Y+2n\) 属于同一个集合，则是假话。
遇到“2 X Y”，则说明需要：
- 合并 \(X\) 和 \(Y+n\)；
- 合并 \(X+n\) 和 \(Y+2n\)；
- 合并 \(X+2n\) 和 \(Y\)。
本文共计499个文字，预计阅读时间需要2分钟。
题目链接：https://www.luogu.com.cn/problem/P2024解题思路：我们用 $X+n$ 来表示吃 $X$ 的集合，用 $X+2n$ 来表示被 $X$ 吃的集合，同时可以推导出 $X$ 的值。题目链接：https://www.luogu.com.cn/problem/P2024 解题思路：我们用吃来表示集合，用被吃来表示另一个集合，通过这种关系可以推导出 $X$ 的值。
解题思路：我们用 \(X+n\) 来表示 吃 \(X\) 的集合，用 \(X+2n\) 来表示被 \(X\) 吃的集合，同时可以推导出 \(X+2n\) 是吃 \(X+n\) 的。
遇到“1 X Y”，则说明需要：
- 合并 \(X\) 和 \(Y\)；
- 合并 \(X+n\) 和 \(Y+n\)；
- 合并 \(X+2n\) 和 \(Y+2n\)。
但是在此之前需要先判断：如果 \(X\) 和 \(Y+n\) 或者 \(Y+2n\) 属于同一个集合，则是假话。
遇到“2 X Y”，则说明需要：
- 合并 \(X\) 和 \(Y+n\)；
- 合并 \(X+n\) 和 \(Y+2n\)；
- 合并 \(X+2n\) 和 \(Y\)。