记录编号 570334 评测结果 AAAAAAAAAA
题目名称 [NOI 2001]食物链 最终得分 100
用户昵称 Gravatarムラサメ 是否通过 通过
代码语言 C++ 运行时间 0.041 s
提交时间 2022-03-28 07:04:02 内存使用 2.81 MiB
显示代码纯文本
#include<bits/stdc++.h>
using namespace std;
int fa[300005];
int n,k,ans;
int find(int x){
	if(x!=fa[x]){
		fa[x]=find(fa[x]);
	}
	return fa[x];
}
void merge(int x,int y){
	int r1=find(fa[x]),r2=find(fa[y]);
	fa[r1]=r2;
}
int main(){
	freopen("eat.in","r",stdin);
	freopen("eat.out","w",stdout);
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>k;
	for(int i=1;i<=3*n;++i){
		fa[i]=i;
	}
	int x,y,w;
	for(int i=1;i<=k;++i){
		cin>>w>>x>>y;
		if(x>n||y>n){
			ans++;
			continue;
		}
		if(w==1){
			if(find(x+n)==find(y)||find(x+2*n)==find(y)){
				ans++;
				continue;
			}
			merge(x,y);
			merge(x+n,y+n);
			merge(x+2*n,y+2*n);
		}
		else{
			if(w==2){
				if(x==y){
					ans++;
					continue;
				}
				if(find(x)==find(y)||find(x+2*n)==find(y)){
					ans++;
					continue;
				}
				merge(x,y+2*n);
				merge(x+n,y);
				merge(x+2*n,y+n);
			}
		}
	}
	cout<<ans<<endl;
	return 0;
}