离散化+并查集,对e排了个序,WA6个点,看了好久,找不到错误,求助大佬
查看原帖
离散化+并查集,对e排了个序,WA6个点,看了好久,找不到错误,求助大佬
346951
jjb_coder楼主2020/11/24 17:20
#include<iostream>
#include<algorithm>
using namespace std;
const int max_n=1e6+16;
int pre[max_n*2];
int book[max_n*2];//离散化记录 
struct Edge{
	int u;
	int v;
	bool e;
}edge[max_n];
int find(int x){
	if(pre[x]==x){
		return x;
	}
	else{
		return pre[x]=find(pre[x]);
	}
}
void add(int x,int y){
	if(find(x)!=find(y)){
		pre[find(x)]=find(y);
	}
}
bool cmp(Edge x,Edge y){
	return x.e>y.e;
}
int main(void)
{
	int t,n,m;
	int total=0;
	cin>>t;
	while(t--){
		cin>>n;
		total=0; 
		for(int i=0;i<n;i++){
			cin>>edge[i].u>>edge[i].v>>edge[i].e;
			book[i]=edge[i].u;
			book[i+n]=edge[i].v;
			pre[i]=i;
			pre[i+n]=i+n;//初始化 
		}
		sort(book,book+2*n);
		m=unique(book,book+2*n)-book;//m为不重复元素个数 
		for(int i=0;i<n;i++){
			edge[i].u=lower_bound(book,book+m,edge[i].u)-book;
			edge[i].v=lower_bound(book,book+m,edge[i].v)-book;
		}
		sort(edge,edge+n,cmp);
		while(edge[total].e==1){
			add(edge[total].u,edge[total].v);
			total++;
		}
		for(int i=total;i<n;i++){
			if(find(edge[i].u)==find(edge[i].v)){
				cout<<"NO"<<endl;
				break;
			}
		}
		if(total==n){
			cout<<"YES"<<endl;
		}
	}
	return 0;
}
2020/11/24 17:20
加载中...