RT,想用 map 加上并查集草过去,结果挂掉了,不说 TLE,WA 都有。
想知道这份代码在什么数据下会 WA,thx dalao!
#include <bits/stdc++.h>
#define pii pair<int,int>
using namespace std;
int t,n;
vector <pii> p0,p1;
int f[2000010],tnt=1;
int find(int x){
if(x!=f[x]){
f[x]=find(f[x]);
}
return f[x];
}
int main(){
cin>>t;
while(t--){
cin>>n;
p1.clear();
p0.clear();
bool ok=false;
tnt=1;
map <int,int> m;
for(int i=1;i<=2*n;i++){
f[i]=i;
}
while(n--){
int op,x,y;
cin>>x>>y>>op;
if(op==1){
if(!m.count(x)){
m[x]=tnt;
tnt++;
}
if(!m.count(y)){
m[y]=tnt;
tnt++;
}
p1.push_back(make_pair(m[x],m[y]));
}
else{
if(!m.count(x)){
m[x]=tnt;
tnt++;
}
if(!m.count(y)){
m[y]=tnt;
tnt++;
}
p0.push_back(make_pair(m[x],m[y]));
}
}
// cout<<m[1]<<" "<<m[2]<<endl;
if(p1.size()==0||p0.size()==0){
cout<<"YES"<<endl;
continue;
}
for(int i=0;i<p1.size();i++){
f[find(m[p1[i].first])]=find(m[p1[i].second]);
}
for(int i=0;i<p0.size();i++){
if(find(m[p0[i].first])==find(m[p0[i].second])){
ok=true;
cout<<"NO"<<endl;
break;
}
}
if(!ok){
cout<<"YES"<<endl;
}
}
return 0;
}
求 hack 数据,因为第二个点实在太大,调不了,所以只好发帖求助。