RE #2 求调,不会离散化qwq
查看原帖
RE #2 求调,不会离散化qwq
680434
shumu楼主2024/4/9 19:29
#include<bits/stdc++.h>
using namespace std;
int t,n;
struct NODE {
	int a,b,c;
}s[110000];
bool flag=true;
bool cmp(NODE x,NODE y) {
	return x.c>y.c;
}
int p[100000010];
int findx(int x) {
	if(x==p[x]) return x;
	return p[x]=findx(p[x]);
}
void hb(int a,int b) {
	int x,y;
	x=findx(a);
	y=findx(b);
	if(x==y) return;
	p[x]=y;
}
int main() {
	cin>>t;
	while(t>0) {
		t--;
		cin>>n;
		for(int i=1;i<=n;i++) {
			cin>>s[i].a>>s[i].b>>s[i].c;
		}
		for(int i=1;i<=100000010;i++) {
			p[i]=i;
		} 
		sort(1+s,1+s+n,cmp);
		for(int i=1;i<=n;i++) {
			if(s[i].c==1) {
				hb(s[i].a,s[i].b);
			}
			else {
				if(findx(s[i].a)==findx(s[i].b)) {
					flag=false;
					break;	
				}
			}
		}
		if(flag) {
			cout<<"YES"<<endl;
		}
		else {
			cout<<"NO"<<endl;
		}
		memset(s,0,sizeof(s));
		flag=true;
	}
	return 0;
}
2024/4/9 19:29
加载中...