[NOI2001] 食物链

题目链接：##

传送门

题目描述：##

扩展域并查集
三种动物会构成一个食物环，可参考石头剪刀布
由于对于一个(x)有三种关系：

• 同类
• 食物
• 天敌

所以将一个(x)拆分成三个域，然后对于两种操作分别合并同类项
对于(x)和(y)是同类的情况，直接一一对应合并两者的三个域即可。
对于(x)吃(y)的情况，将(x)的同类并(y)的天敌，(x)的食物并(y)的同类，(x)的天敌并(y)的食物

对于(x)和(y)是同类的操作，有两类关系是不合法的：

• (x)吃(y)
• (y)吃(x)
  对于(x)吃(y)的操作，有两类关系是不合法的：
• (x)和(y)是同类
• (y)吃(x)

代码：##

#include<bits/stdc++.h>
#define N 3 * (50000)
using namespace std;
inline int read() {
	int cnt = 0, f = 1; char c;
	c = getchar();
	while (!isdigit(c)) {
		if (c == '-') f = -1;
		c = getchar();
	}
	while (isdigit(c)) {
		cnt = c - '0' + cnt * 10;
		c = getchar();
	}
	return cnt * f;
}
int fa[N], n, k, cnt = 0, opr;
int x, y;
int get_father(int x) {
	if(fa[x] == x) return x;
	return fa[x] = get_father(fa[x]);
}
bool check(int opr, int x, int y) {
	if(x > n || y > n) return false;
	int x1 = get_father(x), x2 = get_father(x + n), x3 = get_father(x + 2 * n);
	int y1 = get_father(y), y2 = get_father(y + n), y3 = get_father(y + 2 * n);
	if (opr == 1) {
		if(x2 == y1) return false;
		if(x1 == y2) return false;
	}
	if (opr == 2) {
		if(x == y) return false;
		if(x1 == y1) return false;
		if(x1 == y2) return false;
	}
	return true;
}
bool merge(int opr, int x, int y) {
	int x1 = get_father(x), x2 = get_father(x + n), x3 = get_father(x + 2 * n);
	int y1 = get_father(y), y2 = get_father(y + n), y3 = get_father(y + 2 * n);
	if (!check(opr, x, y)) return false;
	if (opr == 1) {
		fa[y1] = x1; fa[y2] = x2; fa[y3] = x3;
	}
	if (opr == 2) {
		fa[y1] = x2; fa[y2] = x3; fa[y3] = x1;
	}
	return true;
}
int main() {
	n = read(); k = read();
	for (register int i = 1; i <= 3 * n; i++) fa[i] = i;
	for (register int i = 1; i <= k; i++) {
		opr = read(); x = read(); y = read();
		cnt += !merge(opr, x, y);
	}
	printf("%d", cnt);
	return 0;
}