玄幻60分,我人蒙了.(方法:离散化+查并集)
查看原帖
玄幻60分,我人蒙了.(方法:离散化+查并集)
615236
FF_pigeon楼主2022/12/5 22:41
求dalao帮个忙吧,指出一下问题所在QWQ
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+100;
int n,t1,e,f[2*N],rk[N],a,b,tmp[2*N],fan[2*N],flag,tot;
struct no
{
	int x1;
	int x2;
	int e;
}t[2000100];
bool cmp(no h,no g)
{
	return h.e>g.e;
}
int find(int x)
{
	if(x==f[x]) return x;
	else return f[x]=find(f[x]);
}
void bing (int x,int y)
{
	x=find(x);
	y=find(y);
	if(rk[x]>rk[y])f[y]=x;
	else
	{
		f[x]=y;
		if(rk[x]==rk[y])rk[y]++;
	} 
	
}
int main()
{
	cin >> t1;
	while(t1--)
	{
		cin >> n;
		memset(f,0,sizeof(f));
		memset(tmp,0,sizeof(tmp));
		memset(fan,0,sizeof(fan));
		flag=0;
		for(int i=0;i<n;i++)
		{
			cin >> t[i].x1 >> t[i].x2 >> t[i].e;
			if(t[i].e)
			{
				tmp[++tot]=t[i].x1;
				tmp[++tot]=t[i].x2;
			}
			
		}
		sort(tmp,tmp+tot);
		int len=unique(tmp,tmp+tot)-tmp-1;
		for(int i=0;i<n;i++)
		{
			t[i].x1=lower_bound(tmp,tmp+len,t[i].x1)-tmp;
			t[i].x2=lower_bound(tmp,tmp+len,t[i].x2)-tmp;
		}
		for(int i=1;i<=len;i++)
		{
			f[i]=i;
		}
		sort(t,t+n,cmp);
		for(int i=0;i<n;i++)
		{
			if(t[i].e)bing(t[i].x1,t[i].x2);
			else if(find(t[i].x1)==find(t[i].x2))
			{
				cout << "NO" << endl;
				flag=1;
				break;
			}
			
		}
		if(flag==0)cout << "YES" << endl;
	}
 	return 0;
}
2022/12/5 22:41
加载中...