二三两个点 RE 求调
查看原帖
二三两个点 RE 求调
914079
ylh1230i楼主2023/5/24 18:47
#include<bits/stdc++.h>
#if 0
    #define int long long
#endif

const int N=1e6+10;
int n;
int fa[N];
int new_len;
struct Node{
    int x,y,e;
}a[N];
std::vector<int> veca;
void init(){
    for (int i=0;i<=veca.size();i++){
        fa[i]=i;
    }
}
int find(int x){
    if (x!=fa[x]){
        return fa[x]=find(fa[x]);
    }
    return x;
}
void solve(){
    std::cin>>n;
    veca.clear();
    memset(a,0,sizeof(a));
    memset(fa,0,sizeof(fa));
    for (int i=1;i<=n;i++){
        std::cin>>a[i].x>>a[i].y>>a[i].e;
        veca.push_back(a[i].x);
        veca.push_back(a[i].y);
    }
    std::sort(veca.begin(),veca.end());
    //new_len=std::unique(veca.begin(),veca.end())-veca.begin();
    veca.erase(std::unique(veca.begin(),veca.end()));
    for (int i=1;i<=n;i++){
        a[i].x=std::lower_bound(veca.begin(),veca.end(),a[i].x)-veca.begin();
        a[i].y=std::lower_bound(veca.begin(),veca.end(),a[i].y)-veca.begin();
    }
    init();
    std::sort(a+1,a+1+n,[&](const Node& p1,const Node& p2){
        return p1.e>p2.e;
    });
    for (int i=1;i<=n;i++){
        int x=find(a[i].x);
        int y=find(a[i].y);
        if (a[i].e==1){
            fa[x]=y;
        }
        else if (x==y){
            std::cout<<"NO\n";
            return;
        }
    }
    std::cout<<"YES\n";
}
signed main(){
    int t;
    std::cin>>t;
    while (t--){
        solve();
    }
    return 0;
}

2023/5/24 18:47
加载中...