文章

25

粉丝

0

获赞

0

访问

244826

头像
种类并查集(食物链)
经验总结
发布于2020年4月20日 00:42
阅读数 7239

向量:

#include<iostream>
using namespace std;
const int N = 50010;
int d[N], father[N];
int n, k;
int find(int x){
	if (x == father[x])return x;
	int root = find(father[x]);
	d[x] = (d[x] + d[father[x]]) % 3;
	return father[x] = root;
}
int main(){
	cin >> n >> k;
	for (int i = 0; i <= n; i++){
		father[i] = i;
	}
	int res=0;
	for (int i = 0; i < k; i++){
		int opt, a, b;
		cin >> opt >> a >> b;
		if (a>n || b > n){
			res++;
			continue;
		}
		else if (opt == 2 && a == b){
			res++;
			continue;
		}
		else{
			int x = find(a); int y = find(b);
			if (x == y){
				if ((((d[a] - d[b])%3)+3) % 3 != (opt - 1)){
					res++;
				}
			}
			else{
				father[x] = y;
				d[x] = ((d[b] + opt - 1 - d[a]) +3)% 3;
			}
		}
	}
	cout << res << endl;
	return 0;
}

 



登录后发布评论

暂无评论,来抢沙发