(luogu1955)程序自动分析(NOI2015) 发表于 2021-02-09 | 分类于 solution , 数据结构 , 并查集 原题链接 思路:原先以为是关系并查集, 但题中的关系不符合关系并查集的条件. 实际上只是个普通的并查集. 先将所有等号的条件用并查集处理, 再对不等号的条件进行判断即可. 代码:1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556#include <cstdio>#include <cstring>#include <algorithm>using namespace std;const int Mn(1000050);int fa[Mn*2]; //并查集int ff(int x) { //寻找根 return fa[x] ? (fa[x] = ff(fa[x])) : x; //路径压缩}int merge(int x,int y) { //并查集合并 if(x!=y) { fa[y] = x; }}int a[Mn],b[Mn],c[Mn]; //int arr[Mn*2];int main() { int T; scanf("%d",&T); while(T--) { int n; scanf("%d",&n); for(int i(1);i<=n;++i) { scanf("%d %d %d",a+i,b+i,c+i); arr[i*2-1] = a[i]; arr[i*2] = b[i]; } sort(arr+1,arr+2*n+1); int tn = unique(arr+1,arr+2*n+1) - arr - 1; memset(fa,0,sizeof fa); bool isa(true); for(int i(1);i<=n;++i) { if(c[i]==1) { int x = lower_bound(arr+1,arr+tn+1,a[i]) - arr; int y = lower_bound(arr+1,arr+tn+1,b[i]) - arr; int rx = ff(x), ry = ff(y); merge(rx,ry); } } for(int i(1);i<=n;++i) { if(c[i]==0) { int x = lower_bound(arr+1,arr+tn+1,a[i]) - arr; int y = lower_bound(arr+1,arr+tn+1,b[i]) - arr; int rx = ff(x), ry = ff(y); if(rx==ry) { isa = false; break; } } } printf("%s\n",isa?"YES":"NO"); } return 0;}