[bzoj 4195--Noi2015]程序自动分析

xiaoxiao2021-02-28  24

#include<cstdio> #include<cstring> #include<cmath> #include<algorithm> #include<cstdlib> using namespace std; struct node { int x,y,id; }a[1100000]; struct que { int s,id; que(){s=0;} }b[2100000]; bool cmp(que a,que b) { if(a.s>b.s)return false; if(a.s<b.s)return true; return 0; } int fa[2100000]; int findfa(int x) { if(fa[x]==x)return fa[x]; else { fa[x]=findfa(fa[x]); return fa[x]; } } int main() { int t; scanf("%d",&t); while(t--) { int n,s1=0,s2=0; scanf("%d",&n); for(int i=1;i<=n;i++)a[i].x=a[i].y=0; for(int i=1;i<=n;i++) { int x,y,id; scanf("%d%d%d",&x,&y,&id); b[++s1].s=x;b[s1].id=i; b[++s1].s=y;b[s1].id=i; a[i].id=id; } sort(b+1,b+s1+1,cmp); for(int i=1;i<=s1;i++) { if(b[i].s!=b[i-1].s)s2++; if(a[b[i].id].x==0)a[b[i].id].x=s2; else a[b[i].id].y=s2; } for(int i=1;i<=s2;i++)fa[i]=i; for(int i=1;i<=n;i++) { if(a[i].id==1) { int fx=findfa(a[i].x); int fy=findfa(a[i].y); if(fx!=fy)fa[fx]=fy; } } bool bk=true; for(int i=1;i<=n;i++) { if(a[i].id==0) { int fx=findfa(a[i].x); int fy=findfa(a[i].y); if(fx==fy){bk=false;break;} } } if(bk==false)printf("NO\n"); else printf("YES\n"); } return 0; }