题解

zzh张梓涵

2025-08-06 10:57:44

发布于：浙江

10阅读

0回复

0点赞

除了注意离散化之外，尤其要注意多个数据而带来的每次数据的初始化。
可以注意到当z=1时，他是更重要的，故先把z=1的放在前面，进行合并。
后面z=0时，只需要做一个判断就行了

有帮助，赞一个

去预览

0/2000

全部评论 1

zzh张梓涵

代码：

#include<bits/stdc++.h>
#define ull unsighed long long
#define ll long long
using namespace std;
const int N = 2e5+10;
int fa[N],n,siz[N];
ll sum,cnt;
vector<int> adj[N];
bool f;
map<int,int> mp;
struct node{
	int u,v,z;
}e[N];
void init(){
	mp.clear();
	cin>>n;
	cnt = 0;
	f = true; 
	for(int i = 1;i<=2*n;i++) fa[i] = i,siz[i] = 1;
}
int find(int x){
	if(fa[x]==x) return x;
	fa[x] = find(fa[x]);
	return fa[x];
}

void merge(int u,int v){
	u = find(u),v = find(v);
	if(u==v) return;
//	if(siz[u]<siz[v]){
//		swap(u,v);
//	}
//	siz[u]+=siz[v];
	fa[v] = fa[u];
}

bool cmp(node x,node y){
	return x.z>y.z;
}
void solve(){
	init();
	for(int i = 1;i<=n;i++){
		cin>>e[i].u>>e[i].v>>e[i].z;
		mp[e[i].u] = mp[e[i].v] = 1;
	}
	// 离散化 
	for(auto &i:mp){
		i.second = ++cnt;
	}
	//让1的在前，方便其判断 
	sort(e+1,e+n+1,cmp);
	
	for(int i = 1;i<=n;++i){
		int u = mp[e[i].u],v = mp[e[i].v];
		if(e[i].z==1){
			merge(u,v);
		}
		else{
			if(find(u)==find(v)){
				f = 0;
			}
		}
	}
	cout<<(f?"YES":"NO")<<endl;
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	int _t;
	cin>>_t;
	while(_t--){
		solve();
	}
	return 0;
}

2025-08-06 来自浙江