P2024 [NOI2001] 食物链

#include<bits/stdc++.h>
using namespace std;
const int N = 5e4 + 10;
int fa[3 * N];
int find(int x) {
	return x == fa[x] ? x : fa[x] = find(fa[x]);
}
void unit(int x, int y) {
	int r1 = find(x), r2 = find(y);
	fa[r1] = r2;
}
int main() {
	int n, m;
	cin >> n >> m;
	int ans = 0;
	for (int i = 1; i <= 3*n; i++) fa[i] = i;
	while (m--) {
		int op, x, y;
		cin >> op >> x >> y;
		if (x > n || y > n) { ans++; ; continue; }
		if (op == 1) {
			if (find(x + n) == find(y) || find(y + n) == find(x)) { ans++;; continue; }//x的猎物是y，y的猎物是x
			unit(x, y);
			unit(x + n, y + n);
			unit(x + 2 * n, y + 2 * n);
		}
		else {
			if (find(x) == find(y) || find(y + n) == find(x) || x == y) { ans++; ; continue; }//y与x是同类，y的猎物是x，x==y
			unit(x + n, y);//x的猎物是y的同类,或者说y的同类是x的猎物
			unit(x + n * 2, y + n);//y的猎物是x的天敌
			unit(y + n*2, x);//y的天敌是x
		}
	}
	cout << ans;
	return 0;
}

#include<bits/stdc++.h>
using namespace std;
const int N = 5e4 + 10;
int fa[N];
int d[N];
int find(int x) {
	if (x != fa[x]) {
		int xx = fa[x];
		fa[x] = find(fa[x]);
		d[x] = (d[x] + d[xx]) % 3;
	}
	return fa[x];
}
int main() {
	int n, m;
	cin >> n >> m;
	int ans = 0;
	for (int i = 1; i <= n; i++) fa[i] = i;
	while (m--) {
		int op, x, y;
		cin >> op >> x >> y;
		if (x > n || y > n || (op == 2 && x == y)) { ans++; continue; }
		int fx = find(x), fy = find(y);
		if (op == 1) {
			if (fx == fy) {
				if (d[x] != d[y])ans++;
			}
			else {
				fa[fx] = fy;
				d[fx] = (d[y] - d[x] + 3) % 3;
			}
		}
		else {
			if (fx == fy) {
				int res = (3 + d[x] - d[y]) % 3;//关系，记得取模
				if (res != 1) ans++;
			}
			else {
				fa[fx] = fy;
				d[fx] = (d[y] - d[x] + 4) % 3;
			}
		}
	}
	cout << ans;
	for (int i = 1; i <= 5; i++) cout << d[i] << ' ';
	return 0;
}