记录编号	293322	评测结果	AAAAAAAAAA
题目名称	[NOI 2001]食物链	最终得分	100
用户昵称	dateri	是否通过	通过
代码语言	C++	运行时间	0.101 s
提交时间	2016-08-10 14:32:06	内存使用	0.67 MiB

#include<cstdio>
using namespace std;
int pre[50005],num[50005];//num[i]:1:同类 2:i吃父亲... 3:i被父亲吃... 
int find(int r)
{
	if(pre[r]==r) return r;
	int i=r,j=pre[r];
	r=find(pre[r]);
	if(j!=r)
	{
	  if(num[i]==1&&num[j]==1||num[i]==2&&num[j]==3||num[i]==3&&num[j]==2)
	    num[i]=1,pre[i]=r;
	  else if(num[i]==2&&num[j]==1||num[i]==1&&num[j]==2||num[i]==3&&num[j]==3)
	    num[i]=2,pre[i]=r;
	  else
	    num[i]=3,pre[i]=r;
	}
	return r;
}
int main()
{
  freopen("eat.in","r",stdin);
  freopen("eat.out","w",stdout);
  int i,m,n,t,x,y,ans=0,fx,fy;
  scanf("%d%d",&n,&m);
  for(i=1;i<=n;i++)
    pre[i]=i;
  for(i=1;i<=m;i++)
  {
  	scanf("%d%d%d",&t,&x,&y);
  	if(x>n||y>n)
  	{
  	  ans++;
  	  continue;
	}
  	if(t==2&&x==y)
  	{
  	  ans++;
  	  continue;
	}
	if(t==1)
	{
		fx=find(x),fy=find(y);
		if(fx!=fy)
		{
		  pre[fx]=fy;
		  if(x!=fx&&y!=fy)
		  {
		    if(num[x]==num[y])
	          num[fx]=1;
	        else if(num[x]==1&&num[y]==2||num[x]==2&&num[y]==3||num[x]==3&&num[y]==1)
	          num[fx]=2;
	        else
	          num[fx]=3;
		  }
		  else if(x!=fx&&y==fy)
		  {
		  	if(num[x]==1)
	          num[fx]=1;
	        else if(num[x]==2)
	          num[fx]=3;
	        else
	          num[fx]=2;
		  }
		  else if(x==fx&&y!=fy)
		  {
		  	if(num[y]==1)
	          num[fx]=1;
	        else if(num[y]==2)
	          num[fx]=2;
	        else
	          num[fx]=3;
		  }
		  else
		    num[fx]=1;
		}
		else
		{
		  if(x==fx&&y==fy)
		    continue;
		  else if(x==fx)
		  {
		    if(num[y]!=1)
		      ans++;
		  }
		  else if(y==fy)
		  {
			if(num[x]!=1)
			  ans++;
		  }
		  else if(!(num[x]==1&&num[y]==1||num[x]==2&&num[y]==2||num[x]==3&&num[y]==3))
		    ans++;
		}
	}
	else if(t==2)
	{
		fx=find(x),fy=find(y);
		if(fx!=fy)
		{
		  pre[fx]=fy;
		  if(x!=fx&&y!=fy)
		  {
		    if(num[x]==num[y])
	          num[fx]=2;
	        else if(num[x]==1&&num[y]==2||num[x]==2&&num[y]==3||num[x]==3&&num[y]==1)
	          num[fx]=3;
	        else
	          num[fx]=1;
		  }
		  else if(x!=fx&&y==fy)
		  {
		  	if(num[x]==1)
	          num[fx]=2;
	        else if(num[x]==2)
	          num[fx]=1;
	        else
	          num[fx]=3;
		  }
		  else if(x==fx&&y!=fy)
		  {
		  	if(num[y]==1)
	          num[fx]=2;
	        else if(num[y]==2)
	          num[fx]=3;
	        else
	          num[fx]=1;
		  }
		  else
		    num[fx]=2;
		}
		else if(x==fx&&y==fy)
		{
		  ans++;
		  continue;
		}
		else if(x==fx)
		{
		  if(num[y]!=3)
		    ans++;
		}
		else if(y==fy)
		{
			if(num[x]!=2)
			  ans++;
		}
		else if(!(num[x]==2&&num[y]==1||num[x]==1&&num[y]==3||num[x]==3&&num[y]==2))
		  ans++;
	}
  }
  printf("%d\n",ans);
  return 0;
}