P1955 [NOI2015]程序自动分析
题意
略(中文)
思路
并查集加离散化就OK了
代码
#include<bits/stdc++.h> using namespace std; const int maxn=1e6+10; int fa[maxn]; struct node{ int a,b,op; bool operator <(const node &y) const{ return op>y.op; } }a[maxn]; int t[maxn]; int find(int x){ if(x!=fa[x]) return fa[x]=find(fa[x]); else return x; } void merge(int x,int y){ fa[find(x)]=find(y); } int main(){ int _;scanf("%d",&_); while(_--){ int n;scanf("%d",&n); int tot=0; for(int i=1;i<=n;i++){ scanf("%d%d%d",&a[i].a,&a[i].b,&a[i].op); t[++tot]=a[i].a;t[++tot]=a[i].b; } sort(t+1,t+tot+1); tot=unique(t+1,t+tot+1)-t-1; // printf("tot=%d\n",tot); sort(a+1,a+n+1); for(int i=1;i<=tot;i++) fa[i]=i; int flag=0; for(int i=1;i<=n;i++){ int x=lower_bound(t+1,t+tot+1,a[i].a)-t; int y=lower_bound(t+1,t+tot+1,a[i].b)-t; int fx=find(x),fy=find(y); // printf("x=%d y=%d\n",x,y); // printf("fx=%d fy=%d op=%d\n",fx,fy,op[i]); if(a[i].op==1){ // printf("opo=%d\n",op[i]); merge(fx,fy); } else if(a[i].op==0) { // printf("opo=%d\n",op[i]); if(fx==fy) { // printf("hello\n"); flag=1;break; } } } if(flag) puts("NO"); else puts("YES"); } //system("pause"); }