【题目来源】AcWing237. 程序自动分析 - AcWing题库【题目描述】在实现程序自动分析的过程中常常需要判定一些约束条件是否能被同时满足。考虑一个约束满足问题的简化版本假设x 1 , x 2 , x 3 , … x_1,x_2,x_3,…x1​,x2​,x3​,…代表程序中出现的变量给定n nn个形如x i x j x_ix_jxi​xj​或x i ≠ x j x_i≠x_jxi​xj​的变量相等/不等的约束条件请判定是否可以分别为每一个变量赋予恰当的值使得上述所有约束条件同时被满足。例如一个问题中的约束条件为x 1 x 2 x_1x_2x1​x2​x 2 x 3 x_2x_3x2​x3​x 3 x 4 x_3x_4x3​x4​x 1 ≠ x 4 x_1≠x_4x1​x4​这些约束条件显然是不可能同时被满足的因此这个问题应判定为不可被满足。现在给出一些约束满足问题请分别对它们进行判定。【输入】输入文件的第1 11行包含1 11个正整数t tt表示需要判定的问题个数注意这些问题之间是相互独立的。对于每个问题包含若干行第1 11行包含1 11个正整数n nn表示该问题中需要被满足的约束条件个数。接下来n nn行每行包括3 33个整数i , j , e i,j,ei,j,e描述1 11个相等/不等的约束条件相邻整数之间用单个空格隔开。若e 1 e1e1则该约束条件为x i x j x_ix_jxi​xj​若e 0 e0e0则该约束条件为x i ≠ x j x_i≠x_jxi​xj​。【输出】输出文件包括t tt行。输出文件的第k kk行输出一个字符串YES或者NOYES表示输入中的第k kk个问题判定为可以被满足NO表示不可被满足。【输入样例】2 2 1 2 1 1 2 0 2 1 2 1 2 1 1【输出样例】NO YES【核心思想】问题分析给定t tt组测试数据每组包含n nn个变量之间的相等x i x j x_i x_jxi​xj​或不等x i ≠ x j x_i \neq x_jxi​xj​约束条件判断是否存在一种赋值方案使得所有约束同时满足。这是一个并查集问题关键在于利用相等关系的传递性若x i x j x_i x_jxi​xj​且x j x k x_j x_kxj​xk​则x i x k x_i x_kxi​xk​。算法选择并查集Disjoint Set Union, DSU维护变量的等价类支持O ( α ( n ) ) O(\alpha(n))O(α(n))的合并与查询离散化Hash/Map变量编号可能很大达到10 9 10^9109需要映射为连续的编号两遍扫描策略先合并所有相等关系再检查不等关系是否冲突关键步骤离散化使用unordered_map将原始变量值x , y x, yx,y映射为1 ∼ n 1 \sim n1∼n的连续编号初始化并查集p[i] i每个变量初始独立第一遍处理相等约束e 1 e 1e1对于每个相等约束( x i , x j ) (x_i, x_j)(xi​,xj​)pa find(x_i),pb find(x_j)p[pa] pb将两个等价类合并第二遍检查不等约束e 0 e 0e0对于每个不等约束( x i , x j ) (x_i, x_j)(xi​,xj​)pa find(x_i),pb find(x_j)若pa pb说明x i x_ixi​和x j x_jxj​已在同一等价类与不等约束矛盾输出NO结果若所有不等约束均不矛盾输出YES时间/空间复杂度时间复杂度O ( m ⋅ α ( n ) ) O(m \cdot \alpha(n))O(m⋅α(n))其中m mm为约束条数α \alphaα为阿克曼函数反函数近似常数。离散化O ( m ) O(m)O(m)并查集操作O ( m ⋅ α ( n ) ) O(m \cdot \alpha(n))O(m⋅α(n))空间复杂度O ( n ) O(n)O(n)并查集父节点数组和离散化映射表并查集的核心思想等价类维护将相等的变量归入同一集合利用路径压缩优化查询效率传递闭包相等关系具有传递性并查集天然支持这种闭包计算冲突检测策略必须先处理所有相等关系建立等价类再检查不等关系。若顺序颠倒可能导致错误判断离散化必要性当变量范围极大而实际出现次数较少时通过哈希映射压缩空间适用于变量分组、连通性判断、等价关系推理类问题【算法标签】#并查集【代码详解】#includebits/stdc.husingnamespacestd;constintN200005;// 最大节点数离散化后最多 n 个节点intn,m,T;// n: 离散化后的节点计数, m: 约束条件个数, T: 测试用例数intp[N];// 并查集父节点数组unordered_mapint,intS;// 离散化映射原始变量值 - 连续编号structQuery{intx,y,e;// x,y: 离散化后的变量编号, e: 约束类型1相等0不等}query[N];// 存储所有约束条件// 离散化将原始变量值映射为连续编号从1开始intget(intx){if(S.count(x)0)S[x]n;// 若该值未出现过分配新编号n 从0递增returnS[x];// 返回该变量对应的编号}// 并查集查找路径压缩intfind(intx){if(p[x]!x)p[x]find(p[x]);// 递归查找根节点并压缩路径returnp[x];// 返回根节点}intmain(){cinT;// 读入测试用例数while(T--)// 遍历每个测试用例{n0;// 重置节点计数器用于离散化S.clear();// 清空离散化映射cinm;// 读入约束条件个数for(inti1;im;i){intx,y,e;cinxye;// 读入原始变量值和约束类型query[i]{get(x),get(y),e};// 离散化后存入查询数组}for(inti1;in;i)p[i]i;// 初始化并查集每个节点自成一个集合// 第一遍处理所有 相等 约束e1合并对应集合for(inti1;im;i){if(query[i].e1){intpafind(query[i].x),pbfind(query[i].y);p[pa]pb;// 将 x 所在集合的根指向 y 所在集合的根}}// 第二遍检查所有 不等 约束e0是否产生矛盾boolhas_conflictfalse;for(inti1;im;i){if(query[i].e0){intpafind(query[i].x),pbfind(query[i].y);if(papb)// 若原本应不等的两个变量已在同一集合{has_conflicttrue;// 发现矛盾约束不可同时满足break;}}}if(has_conflict)coutNOendl;// 存在矛盾不可满足elsecoutYESendl;// 无矛盾可以满足}return0;}【运行结果】2 2 1 2 1 1 2 0 NO 2 1 2 1 2 1 1 YES