记录编号	233528	评测结果	AAAAAAAAAA
题目名称	[NOI 2001]食物链	最终得分	100
用户昵称	水墨青花	是否通过	通过
代码语言	C++	运行时间	0.104 s
提交时间	2016-03-05 11:21:25	内存使用	1.07 MiB

#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<cstring>
#include<algorithm>

using namespace std;

struct NODE
{
	int relation;
	int father;
}e[100001];

int same=0;
int eat=1;
int beeaten=2;

void Union(int,int,int);
int Findroot(int);
void Read();
void Work();


int n,k;
int order,x,y;
int wrong=0;

int main()
{
	freopen("eat.in","r",stdin);
	freopen("eat.out","w",stdout);
	
	memset(e,0,sizeof(e));
	
	Read();
	
	printf("%d",wrong);
	
	fclose(stdin);
	fclose(stdout);
	
	return 0;
}

void Read()
{
	scanf("%d%d",&n,&k);
	for(int i=1;i<=n;i++)
	{
		e[i].father=i;
		e[i].relation=same;
	}
	
	Work();	
}

void Work()
{
	for(int i=1;i<=k;i++)
	{
		scanf("%d%d%d",&order,&x,&y);
		
		if(x>n||y>n||(order==2&&x==y))
		{
			wrong++;
	
		}
		
		else
		{
			if(Findroot(x)!=Findroot(y))
			{
				Union(x,y,order);
			}
			else
			{
				if(order==1)
				{
					if(e[x].relation!=e[y].relation)
					{
						wrong++;
			
						continue;	
					}
				}
				else
				{
					if(order-1!=((3-e[y].relation)+e[x].relation)%3)
					{
						wrong++;
			
						continue;
					}
				}
			}
		}	
	}
}

void Union(int a,int b,int o)
{
	int r=e[a].father;	//一定要注意递归时原值的存储！！！ 
	e[e[a].father].father=e[b].father;
	e[r].relation=((3-e[a].relation)+(o-1)+e[b].relation)%3;	

}

int Findroot(int a)
{
	if(e[a].father!=a)
	{
		int r=e[a].father; //一定要注意递归时原值的存储！！！ 
		e[a].father=Findroot(e[a].father);
		e[a].relation=(e[a].relation+e[r].relation)%3;
	}
	return e[a].father;
}