本文共 1280 字，大约阅读时间需要 4 分钟。

食物链

题目链接： /

题目大意

有三种动物，关系是 A 吃 B，B 吃 C，C 吃 A。

然后问你有多少句假话。

思路

这道题我们先看到同类，那我们可以想到用并查集。

但是它有吃出环的关系。

这个东西是什么呢？

我们把一个动物拆成三点。

那我们就相同的时候就要求没有吃与被吃的关系，建立就是三个一一对应连通。

听说用带权并查集也可以，但是要分来讨论很多种情况，很麻烦。

代码

#include
   
    using namespace std;int n, k, fa[150001];int op, x, y, ans;int find(int now) {   //并查集	if (fa[now] == now) return now;	return fa[now] = find(fa[now]);}int main() {   	scanf("%d %d", &n, &k);		for (int i = 1; i <= 3 * n; i++)		fa[i] = i;		for (int i = 1; i <= k; i++) {   		scanf("%d %d %d", &op, &x, &y);				if ((x == y && op == 2) || x > n || y > n) {   //第二第三个错误			ans++;			continue;		}				if (op == 1) {   			if (find(x) == find(n + y) || find(x) == find(2 * n + y)) {   //它们已经有吃与被吃的关系了				ans++;				continue;			}			fa[find(x)] = find(y);//建立同类关系			fa[find(n + x)] = find(n + y);			fa[find(2 * n + x)] = find(2 * n + y);		}		else {   			if (find(x) == find(y) || find(x) == find(2 * n + y)) {   //它们已近有同类或反吃关系				ans++;				continue;			}			fa[find(x)] = find(n + y);//建立吃关系			fa[find(n + x)] = find(2 * n + y);			fa[find(2 * n + x)] = find(y);		}	}		printf("%d", ans);		return 0;}