程序自动分析NOI2015

最新推荐文章于 2024-04-24 23:25:43 发布

jmxwzy

最新推荐文章于 2024-04-24 23:25:43 发布

阅读量335

点赞数

分类专栏：并查集

本文链接：https://blog.csdn.net/amdkk/article/details/79306163

版权

并查集专栏收录该内容

2 篇文章

订阅专栏

题目链接https://www.luogu.org/problemnew/show/P1955#sub

被fz大神誉为最水的一道noi题目，是今天并查集的例题，首先拿到这个题时我先想的是如何划分出集合。分别定义a1,a2存储相等条件（x1=y1）和不等条件(x1><y1)，把相等的合并，不相等的条件判断，如果已经合并了的两个数不相等输出no。离散化刚学也不怎么会打就随便模了一个数，emmmmm也就这些代码如下

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
long long fa[1000001];
long long a1[1000001],a2[1000001];
int read()
{
    int w=0,c=1;
    char ch=getchar();
    while (ch<'0' || ch>'9')
      {
        if (ch=='-')
          c=-1;
        ch=getchar();
      }
    while (ch>='0' && ch<='9')
      {
        w=w*10+ch-'0';
        ch=getchar();
      }
    return w*c;
}
int find(int x)
{
	if(fa[x]==x)return fa[x];
	else return fa[x]=find(fa[x]);
}
void unionn(int x,int y)
{
	fa[x]=y;
}
int main()
{
	int t;
	t=read();
	//cin>>t;
	for(int k=1;k<=t;k++)
	{
		
		long long n,x,y,e,tot=0,flag=0;
		n=read();
		//cin>>n;
		for(int i=1;i<=1000001;i++)
		{
			fa[i]=i;
		}
		for(int i=1;i<=n;i++)
		{
			x=read();y=read();e=read();
			//cin>>x>>y>>e;
			x%=521475;
			y%=521475;
			if(e==1)
			{
				int xx=find(x);
				int yy=find(y);
				unionn(xx,yy);
			}
			else
			{
				a1[++tot]=x;
				a2[tot]=y;
			}
		}
		for(int i=1;i<=tot;i++)
			if(find(a1[i])==find(a2[i]))
		        flag=1;
		if(flag==1)cout<<"NO"<<endl;
		else cout<<"YES"<<endl;        
	}
	return 0;
}