题解 | #程序自动分析#

并查集 + 离散化

思路

离散化之后，先执行 op = 1 的，再执行 op = 0 的
执行 op = 1 的时：直接合并
执行 op = 0 的时：进行判断

Code

#include <bits/stdc++.h>

using namespace std;

const int N = 1e7+10;

struct node{
    int x,y;
    int op;    
    bool operator < (const node & a) const{
        return op > a.op  ;
    }    
}p[N];
vector<int> V; 
int fa[N];
int n;

int find(int x){
    if(x==fa[x]) return x;
    return fa[x]=find(fa[x]);
}

int main(){
    int T;  cin>>T;
    while(T--){
        cin>>n;    
        for(int i=0;i<n;i++) {
            int x,y,op;
            cin>>x>>y>>op;
            p[i]={x,y,op};
            V.push_back(x); 
            V.push_back(y);
        }
        sort(p,p+n);
        sort(V.begin(),V.end());
        V.erase(unique(V.begin(),V.end()),V.end());

        for(int i=0;i<n;i++){
            p[i].x=lower_bound(V.begin(),V.end(),p[i].x)-V.begin()+1;
            p[i].y=lower_bound(V.begin(),V.end(),p[i].y)-V.begin()+1;
        }
        for(int i=1;i<=V.size();i++) fa[i]=i;

        bool flag=false;
        for(int i=0;i<n;i++){
            int x=p[i].x,y=p[i].y,op=p[i].op;
            if(op==1) {
                x=find(x),y=find(y);
                if(x!=y) fa[x]=y;
            }
            else{
                x=find(x),y=find(y);
                if(x==y) {    flag=true;    break;    }
            }
        }
        if(flag) puts("NO");
        else puts("YES");
        V.clear();
    }

    return 0;
}