Luogu P1955 [NOI2015] 程序自动分析(并查集）
廉颇老矣，尚能饭否？
题解
并查集动态维护，开始时所有变量构成一个集合，这里我查询了两遍。
第一遍：处理“相等”的条件，合并两个变量所在集合。
第二遍：处理“不等”的条件，用v数组判断，如果两个数之前都有约束过相等，再判断他们是否属于一个集合。否则不用判断，两个变量一定可以符合不等。但是要注意没约束过但i=j的情况，也是不能满足的。
需要注意的是i和j的范围很大，首先要用离散化，把x范围映射在1-2n内，再用并查集完成。
#include<cstdio> #include<cstring> #include<cmath> #include<algorithm> using namespace std; int a[1000005][5],la[1000005],lb[1000005],fa[2000005],n,m; bool v[2000005]; void lsh() //离散化 { int i; sort(la+1,la+2*n+1); m=0; for(i=1;i<=2*n;i++) if(i==1||la[i]!=la[i-1]){m++;lb[m]=la[i];} for(i=1;i<=n;i++) { a[i][1]=lower_bound(lb+1,lb+m+1,a[i][1])-lb; a[i][2]=lower_bound(lb+1,lb+m+1,a[i][2])-lb; } } int get(int x) { if(x==fa[x])return x; return fa[x]=get(fa[x]); } int main() { int t,i,x,y,z,o,bj; scanf("%d",&t); while(t--) { bj=0; memset(a,0,sizeof(a)); memset(la,0,sizeof(la)); memset(lb,0,sizeof(lb)); scanf("%d",&n); for(i=1;i<=n;i++) { scanf("%d%d%d",&x,&y,&z); if(x>y){o=x;x=y;y=o;} a[i][1]=x;a[i][2]=y;a[i][3]=z; la[2*i-1]=x;la[2*i]=y; } lsh(); for(i=1;i<=2*n;i++) fa[i]=i; for(i=1;i<=n;i++) { if(a[i][3]==1) { fa[get(a[i][2])]=get(a[i][1]); v[a[i][1]]=1; v[a[i][2]]=1; } } for(i=1;i<=n;i++) { if(a[i][3]==0&&a[i][1]==a[i][2]) { bj=1; printf("NO "); break; } if(a[i][3]==0&&v[a[i][1]]==1&&v[a[i][2]]==1) { if(fa[get(a[i][1])]==fa[get(a[i][2])]) { bj=1; printf("NO "); break; } } } if(bj==0)printf("YES "); } return 0; }