题解
离散化+并查集。
用并查集维护的是相等关系。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
using namespace std;
int T,n,rec[100005][3],sma[200005],cnt
,par[400005],tmp[200005];
int read(){
int x=0;char ch=getchar();
while(ch<'0'||ch>'9')ch=getchar();
while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
return x;
}
void pre(){
register int i;
n=read();
for(i=0;i<n;i++)
rec[i][0]=read(),rec[i][1]=read(),rec[i][2]=read(),
sma[i]=rec[i][0],sma[i+n]=rec[i][1];
sort(sma,sma+n+n);
for(i=0,cnt=0;i<n+n;i++){
while(i<n+n&&sma[i]==sma[i+1])i++;
tmp[cnt++]=sma[i];
}
for(i=0;i<cnt+cnt;i++)
par[i]=i;
for(i=0;i<n;i++)
rec[i][0]=lower_bound(tmp,tmp+cnt,rec[i][0])-tmp,
rec[i][1]=lower_bound(tmp,tmp+cnt,rec[i][1])-tmp;
//,printf("%d:%d %d\n",i,rec[i][0],rec[i][1]);
}
int find(int a){
if(par[a]==a)return a;
return (par[a]=find(par[a]));
}
inline void unite(int a,int b){
par[find(a)]=find(b);
}
bool solve(){
int i;
for(i=0;i<n;i++)
if(rec[i][2])
unite(rec[i][0],rec[i][1]);
for(i=0;i<n;i++)
if(!rec[i][2])
if(find(rec[i][0])==find(rec[i][1]))return false;
return true;
}
int main(){
T=read();
while(T--){
pre();
printf("%s\n",solve()?"YES":"NO");
}
return 0;
}