WA on #3#4##8 map + 并查集
查看原帖
WA on #3#4##8 map + 并查集
373198
WhileTrueRP楼主2023/7/15 09:17
#include<map>
#include<iostream>
#include<algorithm>
using namespace std;
#define N 2000005
map<int,int> maps;
struct node{
    int x;
    int y;
    int z;
}a[N];
int f[N];
int findn(int t){
    return f[t]==t?t:f[t]=findn(f[t]);
}   
bool cmp(node x,node y){
	return x.z>y.z;
}
int main(){
    int t;
    cin>>t;
    while(t--){
        bool flag = true;
        int n;
        cin>>n;
        for(int i=1;i<=2*n+1;i++){
            f[i] = i;
        }
        for(int i=1;i<=n;i++){
            cin>>a[i].x>>a[i].y>>a[i].z;
        }
        sort(a+1,a+1+n,cmp);
        int i=1,j=1;
		while(a[i].z == 1){
            int xx,yy;
        	auto iter = maps.find(a[i].x);
        	if(iter != maps.end()){
        		xx = findn(iter->second);
			}else{
				maps.insert(pair<int,int>(a[i].x,j));
                xx = findn(j);
				j++;
			}
			iter = maps.find(a[i].y);
			if(iter != maps.end()){
        		yy = findn(iter->second);
			}else{
				maps.insert(pair<int,int>(a[i].y,j));
                yy = findn(j);
				j++;
			}
            if(xx!=yy){
                f[xx] = yy;
                //cout<<"{"<<xx<<","<<yy<<"}";
            }
			i++;
		}
        while(i<=n){
            int xx,yy;
        	auto iter = maps.find(a[i].x);
        	if(iter != maps.end()){
        		xx = findn(iter->second);
			}else{
				maps.insert(pair<int,int>(a[i].x,j));
				j++;
			}
			iter = maps.find(a[i].y);
			if(iter != maps.end()){
        		yy = findn(iter->second);
			}else{
				maps.insert(pair<int,int>(a[i].y,j));
				j++;
			}
            //cout<<"["<<xx<<","<<yy<<"]";
            if(xx==yy){
                flag = false;
            }
			i++;
        }
        cout<<((flag == true)?"YES\n":"NO\n");
        maps.clear();
    }
}
2023/7/15 09:17
加载中...