记录编号	516939	评测结果	AAAAAAAAAA
题目名称	[NOI 2001]食物链	最终得分	100
用户昵称	梦那边的美好ET	是否通过	通过
代码语言	C++	运行时间	0.076 s
提交时间	2018-10-26 21:02:59	内存使用	0.70 MiB

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
int n,k,ans=0,fa[50010],r[50001],d,x,y;
int find(int x){
	if(x!=fa[x]){
		int fx=find(fa[x]);
		r[x]=(r[x]+r[fa[x]])%3;fa[x]=fx;
	}
	return fa[x];
}
bool add(int d,int x,int y){
	int fx=find(x),fy=find(y);
	if(fx==fy){
		if((r[y]+3-r[x])%3!=d)return 1;
		else return 0;
	}
	fa[fy]=fx;r[fy]=(-r[y]+d+r[x]+3)%3;
	return 0;
}
int main(){
	freopen("eat.in","r",stdin);
	freopen("eat.out","w",stdout);
	scanf("%d%d",&n,&k);
	for(int i=1;i<=n;i++)fa[i]=i,r[i]=0;
	for(int i=1;i<=k;i++){
		scanf("%d%d%d",&d,&x,&y);
		if(x>n||y>n||(x==y&&d==2)){ans++;continue;}
		if(add(d-1,x,y))ans++;
	}
	printf("%d",ans);
	return 0;
}