BZOJ 4195 [Noi2015]程式自動分析 - 并查集

NOI那年怎麼全是大水題。。。要是我能在考場上見到一回就好了233

這裡需要注意一個問題，不能采用合并取反的數，因為取反意為不等，而x!=y，y!=z而x==z可以成立，一定要記住，沒事别取反，總想搞個大新聞。。。

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

using namespace std;

const int maxn=1000005;

int n,T;
int disc[maxn<<1],fa[maxn];
bool op[maxn];

struct query
{
	int x,y,op;
}q[maxn];

int read()
{
	int x=0;char ch=getchar();
	while(ch<'0'||ch>'9')ch=getchar();
	while(ch<='9'&&ch>='0')x=x*10+ch-'0',ch=getchar();
	return x;
}
int find(int x)
{
	return fa[x]==x?x:fa[x]=find(fa[x]);
}
int main()
{
	scanf("%d",&T);
	while(T--)
	{
		bool ok=true;
		scanf("%d",&n);
		int cnt=0;
		for(int i=1;i<=n;i++)
			disc[++cnt]=q[i].x=read(),
			disc[++cnt]=q[i].y=read(),
			q[i].op=read();
		sort(disc+1,disc+cnt+1);
		int num=unique(disc+1,disc+cnt+1)-(disc+1);
		
		for(int i=1;i<=num;i++)fa[i]=i;
		for(int i=1;i<=n;i++)if(q[i].op)
		{
			int fx=find(lower_bound(disc+1,disc+num+1,q[i].x)-disc);
			int fy=find(lower_bound(disc+1,disc+num+1,q[i].y)-disc);
			if(fx!=fy)fa[fx]=fy;
		}
		for(int i=1;i<=n;i++)if(!q[i].op)
		{
			int fx=find(lower_bound(disc+1,disc+num+1,q[i].x)-disc);
			int fy=find(lower_bound(disc+1,disc+num+1,q[i].y)-disc);
			if(fx==fy)
			{
				ok=false;
				break;
			}
		}
		printf("%s\n",ok?"YES":"NO");
	}
	return 0;
}