食物链大全_食物链有哪几种类型

食物链是并查集中的一道经典题, 第一次看《挑战程序设计竞赛》上懵懵懂懂, 最近又看见了发现还是一脸懵逼。

首先题目如下

动物王国中有三类动物 A,B,C，这三类动物的食物链构成了有趣的环形。 A 吃 B，B 吃 C，C 吃 A。 现有 N 个动物，以 1∼N 编号。 每个动物都是 A,B,C 中的一种，但是我们并不知道它到底是哪一种。 有人用两种说法对这 N 个动物所构成的食物链关系进行描述： 第一种说法是 1 X Y，表示 X 和 Y 是同类。 第二种说法是 2 X Y，表示 X 吃 Y。 此人对 N 个动物，用上述两种说法，一句接一句地说出 K 句话，这 K 句话有的是真的，有的是假的。 当一句话满足下列三条之一时，这句话就是假话，否则就是真话。 当前的话与前面的某些真的话冲突，就是假话； 当前的话中 X 或 Y 比 N 大，就是假话； 当前的话表示 X 吃 X，就是假话。 你的任务是根据给定的 N 和 K 句话，输出假话的总数。 

第一次见可能不知道怎么用并查集维护这么多种集合, 甚至像我一样看了白书上的讲解还是不太懂, 下面是我重新思考了一下, 并看了y总的另一种讲解得出的一下总结。

一、维护所有的组合来判断关系

白书上的代码就是维护的所以组合, 但我一开始并没看懂。。。
首先我们先用一个3 * N 的数组建立并查集，每 N 个区间代表的是一种类型，想下面这样。

为了简洁, 下面对于三个区间分别称为 N, 2N, 3N

注意这里要抽象出来，不能理解为具体的A类、B类，因为题目中三者的关系是一个环, 所以只要记住 N 内的动物能吃 2N 内的动物，而 2N内的动物能吃 3N 内的动物, 然后 3N 内的动物能吃第 N 内的动物

然后在这个 3 * N 的并查集里面, 会有很多个集合, 而每一个集合都是一组关系, 举个栗子:
a 可以吃 b, 那么 a b 就是一个集合里的, 而上面的关系中有三种捕食关系, 所以 a 吃 b 有三种情况，一个是 a 是 N 内的, 则 b 就是2N内的(因为 N 可以吃 2N), 这时候数组中 a 和 b + N 就要成为一个集合；第二个是 a 是第 2N 内的, 则 b 就是 3N 内的, a + N 和 b + 2 * N 就是一个集合了； 同理第三种情况a + 2 * N 和 b 就是一个集合。

注意这里 a, b 在不同的 N 区域内的性质不一样, 虽然都是a, b，但是他们代表的是不同物种的a, b，也就是说如果 a 和 b + N 在一个集合里，则这个集合存在 a 吃 b 的关系, 如果 a 和 b + 2N 在同一组，则存在 b 吃 a 的关系，等等…

对于题目的具体做法 :

首先判断它们是否是一个集合中的，即判断是否已经有关系了

如果 x 和 y 在同一个集合中

这时候就要判断 xy 已有的关系是否和所给的关系矛盾, 例如 x 和 y + N (第二组中的 y) 是同一个集合, 这说明 x 能吃 y，因此 x 和 y 是同类与 y 能吃 x 就是谎言。

注意这里不需要判断另外两种关系是否合法(第二组的x和第三组的y，第三组的x和第一组的y)，因为在下面合并过程中，我们把每种情况都保存下来了，如果 x 和 y + n 是一组，则必有 x + n 和 y + 2 * n 和 x + 2 * n 和 y 是同一组，所以只需要判断一种情况就行。

如果不在同一个集合

就需要把两个集合合并, 而他们是同类的可能有三种, 即同为第一种, 第二种和第三种。

具体代码如下 :

#include <iostream> #include <string> #include <algorithm> #include <set> #include <map> #include <unordered_set> #include <unordered_map> #include <stack> #include <queue> #include <cstdlib> #include <cstring> using namespace std; #define mst(a, b) memset(a, b, sizeof(a)) typedef long long ll; typedef pair<int, int> pii; const int maxn =  + 10; const int inf = INT32_MAX; int n, k; int fa[maxn * 3], cnt; int find(int x) { 
    return fa[x] = fa[x] == x ? x : find(fa[x]); } void merge(int x, int y) { 
    fa[find(x)] = find(y); } int main() { 
    std::ios::sync_with_stdio(false); cin >> n >> k; for (int i = 0; i <= n * 3 + 10; i++) fa[i] = i; while (k--) { 
    int d, x, y; cin >> d >> x >> y; if (x <= 0 || x > n || y <= 0 || y > n) { 
    cnt += 1; continue; } if (d == 1) { 
    if (find(x) == find(y + n) || find(x) == find(y + 2 * n)) { 
    // 如果 x 能吃 y, 或者 x 能被 y 吃, 则为谎言 cnt += 1; } else { 
    // 否则 xy 合并为同一种 merge(x, y); // 同为第一种 merge(x + n, y + n); // 同为第二种 merge(x + 2 * n, y + 2 * n); // 同为第三种 } } else { 
    if (find(x) == find(y) || find(x) == find(y + 2 * n)) { 
    // 如果 x 和 y 是同一种 或者 x 能被 y 吃, 则为谎言 cnt += 1; } else { 
    // 否则合并 x 能吃 y merge(x, y + n); // 第一种生物的 x 能吃 y merge(x + n, y + 2 * n); // 第一种生物x 能吃 y merge(x + 2 * n, y); // .... } } } cout << cnt << endl; return 0; } 

二、通过根节点判断关系

这种方法是在 acWing 上y总讲的， 第一次听的时候有点懵，听第二遍才发现是真的妙，我把主要的思路说一下(强烈推荐y总的课，讲得算法很全很详细，而且价格也不是太贵)
因为关系是个三个节点的环，所以我们假设父节点被子节点吃，则可以确定子节点的子节点可以吃父节点，即：

注意这里说的根节点指的是并查集中每一个集合的祖先

然后可以发现能吃根节点的到根节点的距离为 1， 能被根节点吃的到根节点的距离为 2，和根节点属于同一类的距离为 3，如果向下多画几个几点，你会发现他们 模 3 之后的值分别是 1 2 0，所以只要确定了和根节点的距离，就可以确定他们之间的关系。
举个栗子:
如果 a 节点到 根节点的距离 mod 3 = 1，b 节点 mod 3 = 2，这说明 a 能吃根节点，b 能被 根节点吃，根据关系可以推出 b 能 吃 a，他们之间的距离关系就是 : dis(a) % 3 + 1 = dis(b) % 3 ⇒ (dis(a) – dis(b) + 1) % 3 = 0
即 (dis(b) – dis(a) – 1) % 3 = 0

dis(x) 表示 x 到根节点的距离

如果 a 节点和 b 节点 mod 3 相等，说明他们是同一类，距离关系就为:
dis(a) % 3 = dis(b) % 3 ⇒ (dis(a) – dis(b)) % 3 = 0

这样我们就可以用上面两个等式来判断 a 和 b 如果在一个集合中，他们的关系是同一类还是捕食。

在合并节点的时候需要更新他们到根节点的距离:

如果 a 和 b 是同一类

则他们合并之后 a、b 到根节点的距离 mod 3 还是为0，如果以 a 向 b 合并

则有 (dis(a) + D) % 3 = dis(b) % 3，即 (dis(a) + D – dis(b)) % 3 = 0
要使上面等式为0，则 D 明显为 dis(b) – dis(a)，所以在合并的时候，a的距离只要更新为 dis(b) – dis(a) 就可以了

如果 a 吃 b

同理
则 (dis(a) – 1 + D) % 3 = dis(b) % 3 ⇒ (dis(a) + D – dis(b) – 1) % 3 = 0
所以只要更新 a 的距离为 dis(b) – dis(a) + 1 就彳亍。

具体代码：

#include <iostream> #include <string> #include <algorithm> #include <set> #include <map> #include <unordered_set> #include <unordered_map> #include <stack> #include <queue> #include <cstdlib> #include <cstring> using namespace std; #define mst(a, b) memset(a, b, sizeof(a)) typedef long long ll; typedef pair<int, int> pii; const int maxn =  + 10; const int inf = INT32_MAX; int fa[maxn], d[maxn]; int n, k, cnt; int find(int x) { 
    if (x != fa[x]) { 
    int u = fa[x]; // 保存 x 的祖先 fa[x] = find(fa[x]); // 更新 x 集合 d[x] += d[u]; // 更新x 到根节点的距离(x 到自己以前的根节点的 // 距离 + 以前根节点到新根节点的距离) } return fa[x]; } void merge(int x, int y) { 
    fa[find(x)] = find(y); } int main() { 
    std::ios::sync_with_stdio(false); cin >> n >> k; for (int i = 0; i <= n; i++) fa[i] = i; while (k--) { 
    int op, x, y; cin >> op >> x >> y; if (x > n || y > n) { 
    cnt += 1; continue; } int fx = find(x), fy = find(y); if (op == 1) { 
    if (fx == fy && (d[x] - d[y]) % 3) { 
    // 如果 x 和 y 在同一集合, 且 x 和 y 不是同一类 cnt++; } else if (fx != fy) { 
    // 合并两个集合 d[fx] = d[y] - d[x]; fa[fx] = fy; } } else { 
    if (fx == fy && (d[x] - d[y] - 1) % 3) { 
    // 如果 x 和 y 在同一集合, 且 x 不能吃 y cnt++; } else if (fx != fy) { 
    // 不是一个集合就合并 d[fx] = d[y] - d[x] + 1; fa[fx] = fy; } } } cout << cnt << endl; return 0; } 

这种方法 y 总讲得真的非常详细，对竞赛有兴趣的可以考虑一下 acWing 的算法课。