题解 | 人人都是好朋友

并查集+离散化一下就行了，dsu随便写的，没按秩合并什么的，跑的1.6s，常数可能有点，离散化写的也有点丑陋了

struct DSU{
    int n;
    vector<int> f;
    void init(int _){
        n=_;
        f.resize(n+1);
        for(int i=1;i<=n;i++){
            f[i]=i;
        }
    }
    int find(int x){
        if(x==f[x])return x;
        else{
            return f[x]=find(f[x]);
        }
    }
    void merge(int x,int y){
        x=find(x);
        y=find(y);
        if(x==y)return ;
        f[x]=y;
        return ;
    }
    bool same(int x,int y){
        return find(x)==find(y);
    }
};
int p(int x,vector<int> &v){
    int L=0,R=v.size(),pos=-1;
    while(L<=R){
        int mid=(L+R)>>1;
        if(v[mid]<=x){
            pos=mid;
            L=mid+1;
        }else{
            R=mid-1;
        }
    }return pos;
}
void solve(){
    int n;
    cin>>n;
    vector<pair<int,int>>q,r;
    vector<int> k;
    for(int i=1;i<=n;i++){
        int a,b,c;
        cin>>a>>b>>c;
        if(c!=1){
            q.push_back({a,b});
        }else{
            r.push_back({a,b});
        }
        k.push_back(a);
        k.push_back(b);
    }
    sort(k.begin(),k.end());
    k.erase(unique(k.begin(),k.end()),k.end());
    unordered_map<int,int>f;
    DSU d;
    d.init(k.size()+1);
    for(int i=0;i<r.size();i++){
        int u,v;
        if(f.find(r[i].first)==f.end()){
            f[r[i].first]=p(r[i].first,k);
        }
        u=f[r[i].first];
        if(f.find(r[i].second)==f.end()){
            f[r[i].second]=p(r[i].second,k);
        }
        v=f[r[i].second];
        d.merge(u,v);
    }
    for(int i=0;i<q.size();i++){
        int u,v;
        if(f.find(q[i].first)==f.end()){
            f[q[i].first]=p(q[i].first,k);
        }
        u=f[q[i].first];
        if(f.find(q[i].second)==f.end()){
            f[q[i].second]=p(q[i].second,k);
        }
        v=f[q[i].second];
        if(d.same(u,v)){
            cout<<"NO"<<'\n';
            return ;
        }
    }cout<<"YES"<<'\n';
}