求助 P1955

代码如下

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
int read();
int t;
int f[N*5];
map <int,int> p;
struct Node{
	int x,y,opt;
}q[N];
int find(int x)
{
	if(f[x]==x) return x;
	return f[x]=find(f[x]);
}
void solve()
{
	p.clear();
	int n=read(),cnt=0,flag=1;
	for(int i=1;i<=n;i++)
	{
		q[i].x=read(); q[i].y=read(); q[i].opt=read();
		if(!p[q[i].x]) p[q[i].x]=++cnt;
		if(!p[q[i].y]) p[q[i].y]=++cnt;
	}
	for(int i=1;i<=cnt+cnt+cnt;i++) f[i]=i;
	for(int i=1;i<=n;i++)
	{
		int opt=q[i].opt,x=p[q[i].x],y=p[q[i].y];
		if(opt==1)
		{
			if(find(x)==find(y+cnt) || find(x+cnt)==find(y)) flag=0;
			else
			{
				f[find(x)]=find(y);
				f[find(x+cnt)]=find(y+cnt);
			}
		}
		else
		{
			if(find(x)==find(y) || find(x+cnt)==find(y+cnt)) flag=0;
			else
			{
				f[find(x)]=find(y+cnt);
				f[find(y)]=find(x+cnt);
			}
		}
	}
	else printf("NO");
	putchar('\n');
}
int main()
{
	t=read();
	for(int i=1;i<=t;i++) solve();
	return 0;
}
int read()
{
	int x=0,f=1; char ch=getchar();
	while(ch<'0' || ch>'9')
	{
		if(ch=='-') f=-1;
		ch=getchar();
	}
	while(ch>='0' && ch<='9')
	{
		x=(x<<1)+(x<<3)+(ch^48);
		ch=getchar();
	}
	return x*f;
}