在实现程序自动分析的过程中,常常需要判定一些约束条件是否能被同时满足。 考虑一个约束满足问题的简化版本：假设x1,x2,x3,…代表程序中出现的变量，给定n个形如xi=xj或xi≠xj的变量相等/不等的约束条件，请判定是否可以分别为每一个变量赋予恰当的值，使得上述所有约束条件同时被满足。例如，一个问题中的约束条件为：x1=x2，x2=x3，x3=x4，x1≠x4，这些约束条件显然是不可能同时被满足的，因此这个问题应判定为不可被满足。 现在给出一些约束满足问题，请分别对它们进行判定。
这道题看到x?的范围这么大，但又与n的范围差那么远，就肯定要离散化。之后呢，由于这只是判断是否满足条件，便把相等的归为一类，所以便用并查集。先把相等的操作该做了，之后再针对不相等的判断一下是否满足条件就可以了。
#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; }