题解（并查集+离散化）

666我服了，卡着我一个TLE，只能开个快读（懒得用scanf）

#include<iostream>
#include<algorithm>
#include<map>
using namespace std;
const int N=2e5+1;
struct node{
long long i,j,e;
}s[N];
bool cmp(node a,node b){
    return a.e>b.e;
}
int f[N];//代表i的祖先
int find(int x){//找x的祖先 
	if(f[x]==x)return x;
	return f[x]=find(f[x]);//当前x的祖先
	//find(f[x])找x祖先的祖先 
} 
void unite(int x,int y){
	int rootx=find(x);//找x的祖先
	int rooty=find(y);//找y的祖先
	//如果x和y的祖先不同 就把y设为x祖先的祖先 
	if(rootx!=rooty)f[rootx]=rooty; 
}
void solve(){
    int n;
    cin>>n;
    map<int,int>mp;
    int cnt=0;
    for(int i=1;i<=n;i++){
        int x,y,z;
        cin>>x>>y>>z;
        if(!mp.count(x))mp[x]=++cnt;
        if(!mp.count(y))mp[y]=++cnt;
        s[i]={mp[x],mp[y],z};
    }
    sort(s+1,s+1+n,cmp);
    for(int i=1;i<=cnt;i++)f[i]=i;
    for(int i=1;i<=n;i++){
        if(s[i].e==1)
            unite(s[i].i,s[i].j);
        else if(find(s[i].i)==find(s[i].j)){//i==j e==0 xi!=xj冲突
            cout<<"NO\n";
            return ;
        }
    }
    cout<<"YES\n";
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
	int t;
	cin>>t;
    while(t--){
    	solve();
    }
	return 0;
}