题目链接:http://acm.sdibt.edu.cn:8080/judge/contest/view.action?cid=357#problem/A
关键偏移量的理解,在此不再赘述,代码如下:

#include <stdio.h>
#include <string.h>
int N,K;
int de[50000],fa[50000];
void init()  //初始化
{
	int i;
	for(i=1;i<=N;i++)
	{
		de[i]=0;
		fa[i]=i;
	}
}
int find(int x)
{ 
    int tx;//x祖先
	if(x==fa[x])
		return x;
	tx=find(fa[x]);
	de[x]=(de[x]+de[fa[x]])%3;//向量关系解决
	return fa[x]=tx;//压缩路径
}
int unio(int x,int y,int type)
{    
	int tx,ty;
    if(x>N||y>N) //前两种不符合的情形
		return 1;
	if(type==1&&x==y)
		return 1;
    tx=find(x);
	ty=find(y);
	if(tx==ty)//在一个集合时,判断是否符合描述
	{
		if((de[y]-de[x]+3)%3!=type)
			return 1;
		else
			return 0;
	}
	else
	{
		fa[ty]=tx;//合并
		de[ty]=(de[x]-de[y]+type+3)%3;//方法同上
		return 0;
	}
}
int main()
{
  int type,i,count,x,y;
	  count=0;
	  scanf("%d%d",&N,&K);
      init();
	  for(i=1;i<=K;i++)
	  {    
		  scanf("%d%d%d",&type,&x,&y);
		  if(unio(x,y,type-1)==1)
             count++;
	  }
	  printf("%d\n",count);
  return 0;
}

不当之处,欢迎指正!

发表评论

电子邮件地址不会被公开。

Post Navigation