2803028_ac_138ms_464k.c

北大大牛代码 1240道题的原代码 超级权威

#include <stdio.h>
#include <string.h>

int n, k;
int fal;
int fa[50001], ch[50001];

int fath(int x)
{
	int k;

	if(fa[x]==0)
		return x;
	if(fa[fa[x]]==0)
		return fa[x];
	k = fath(fa[x]);
	ch[x] = (ch[x]+ch[fa[x]])%3;
	fa[x] = k;
	return k;
}

void solve(int d,int x,int y)
{
	int p, q;

	p = fath(x);
	q = fath(y);
	if(p==q)
	{
		if((3-ch[x]+ch[y])%3!=d)
			fal++;
		return ;
	}
	fa[q] = p;
	ch[q] = (3+d+ch[x]-ch[y])%3;
}

int main()
{
	int i;
	int d, x, y;

	scanf("%d%d",&n,&k);
	memset(fa,0,sizeof(fa));
	memset(ch,0,sizeof(ch));
	fal = 0;
	for(i = 0; i < k; i++)
	{
		scanf("%d%d%d",&d,&x,&y);
		if(x > n||y > n||(d==2&&x==y))
		{
			fal ++;
			continue;
		}
		if(x==y)
			continue;
		solve(d-1,x,y);
	}
	printf("%d\n",fal);
	return 0;
}