33题食物链是什么？

33.Acwing基础课第240题-中等-食物链 题目描述 \(动物王国中有三类动物 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 句话，输出假话的总数。\) 输入格式 \(第一行是两个整数 N 和 K，以一个空格分隔。\) \(以下 K 行每行是三个正整数 D，X，Y，两数之间用一个空格隔开，其中 D 表示说法的种类。\) \(若 D=1，则表示 X 和 Y 是同类。\) \(若 D=2，则表示 X 吃 Y。\) 输出格式 只有一个整数，表示假话的数目。 数据范围 \(1≤N≤50000\), \(0≤K≤100000\) 输入样例： 100 7 1 101 1 2 1 2 2 2 3 2 3 3 1 1 3 2 3 1 1 5 5 输出样例： 3 代码： #include <iostream> using namespace std; const int N = 50010; // 最大动物数量 int n, m; // n：动物数 m：语句数 int p[N]; // 并查集父节点数组 int d[N]; // 核心：d[x] 表示 x 到 根节点 的距离（用来表示关系） // 带路径压缩的查找函数，同时更新 d[x]（x到根的距离） int find(int x) { // 如果 x 不是根节点 if (p[x] != x) { // 先递归找到根节点 t int t = find(p[x]); // 更新 d[x]：x 到根的距离 = x 到父节点的距离 + 父节点到根的距离 d[x] += d[p[x]]; // 路径压缩：直接把 x 挂到根节点上 p[x] = t; } // 返回根节点 return p[x]; } int main() { // 读入动物数量 n 和 语句数量 m scanf("%d%d", &n, &m); // 初始化并查集：每个动物自己是一个集合 for (int i = 1; i <= n; i ++ ) p[i] = i; int res = 0; // 记录假话数量 // 处理 m 条语句 while (m -- ) { int t, x, y; // t=1：x和y是同类 t=2：x吃y scanf("%d%d%d", &t, &x, &y); // 条件1：x 或 y 超过 n，假话 if (x > n || y > n) res ++ ; else { // 找到 x 和 y 的根节点 int px = find(x), py = find(y); if (t == 1) // 当前语句：x 和 y 是同类 { if (px == py) // x和y在同一个集合，可以判断关系 { // 如果 (d[x] - d[y]) % 3 != 0，说明不是同类，是假话 if ((d[x] - d[y]) % 3) res ++ ; } else // 不在同一个集合，合并它们 { p[px] = py; // 把 px 挂到 py 上 d[px] = d[y] - d[x]; // 维护距离关系，保证同类 } } else // t == 2，当前语句：x 吃 y { if (px == py) // 在同一个集合，可以判断关系 { // 如果 (d[x] - d[y] - 1) % 3 != 0，说明不是吃的关系，是假话 if ((d[x] - d[y] - 1) % 3) res ++ ; } else // 不在同一个集合，合并 { p[px] = py; // 把 px 挂到 py 上 d[px] = d[y] + 1 - d[x]; // 维护距离关系，保证 x 吃 y } } } } // 输出假话总数 printf("%d\n", res); return 0; }