求助10pts
查看原帖
求助10pts
661595
a2lyaXNhbWUgbWFyaXNh楼主2022/11/24 18:31
#include<bits/stdc++.h>
using namespace std;

const int MAXN=200010;

struct ask{
    int x,y,e;
    bool operator<(const ask &Node){
        return e<Node.e;
    }
}data[MAXN];

class Dsu{
    private:
        int fa[MAXN];
    public:
        inline void init(const int &LEN){
            for(int i=1;i<=LEN;++i)
                fa[i]=i;
        }    
        inline int get(const int &x){
            if(fa[x]==x)
                return x;
            return fa[x]=get(fa[x]);    
        }
        inline bool same_root(const int &x,const int &y){
            return get(x)==get(y);
        }
        inline void merge(const int &x,const int &y){
            if(same_root(x,y))
                fa[get(y)]=get(x);
        }
};

int n,t;

int main(){
    cin>>t;
    while(t--){
        bool f=1;
        Dsu dsu;
        memset(data,0,sizeof(data));
        vector<int>v;
        cin>>n;
        for(int i=1;i<=n;++i){
            cin>>data[i].x>>data[i].y>>data[i].e;
            v.push_back(data[i].x);
            v.push_back(data[i].y);
        }
        sort(v.begin(),v.end());
        v.erase(unique(v.begin(),v.end()),v.end());
        for(int i=1;i<=n;++i){
            data[i].x=lower_bound(v.begin(),v.end(),data[i].x)-v.begin();
            data[i].y=lower_bound(v.begin(),v.end(),data[i].y)-v.begin();
        }
        dsu.init(v.end()-v.begin());
        sort(data+1,data+1+n);
        for(int i=1;i<=n;++i){
            if(data[i].e)
                dsu.merge(data[i].x,data[i].y);
            else if(dsu.same_root(data[i].x,data[i].y)){
                f=0;
                break;
            }   
        }
        if(f)puts("YES");
        else puts("NO");
    }
}
2022/11/24 18:31
加载中...