题解：AcWing 237 程序自动分析

【题目来源】

AcWing：237. 程序自动分析 - AcWing题库

【题目描述】

在实现程序自动分析的过程中，常常需要判定一些约束条件是否能被同时满足。

考虑一个约束满足问题的简化版本：假设x 1 , x 2 , x 3 , … x_1,x_2,x_3,…x1​,x2​,x3​,…代表程序中出现的变量，给定n nn个形如x i = x j x_i=x_jxi​=xj​或x i ≠ x j x_i≠x_jxi​=xj​的变量相等/不等的约束条件，请判定是否可以分别为每一个变量赋予恰当的值，使得上述所有约束条件同时被满足。

例如，一个问题中的约束条件为：x 1 = x 2 x_1=x_2x1​=x2​，x 2 = x 3 x_2=x_3x2​=x3​，x 3 = x 4 x_3=x_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 e=1e=1，则该约束条件为x i = x j x_i=x_jxi​=xj​；若e = 0 e=0e=0，则该约束条件为x i ≠ x j x_i≠x_jxi​=xj​。

【输出】

输出文件包括t tt行。

输出文件的第k kk行输出一个字符串YES或者NO，YES表示输入中的第k kk个问题判定为可以被满足，NO表示不可被满足。

【输入样例】

2 2 1 2 1 1 2 0 2 1 2 1 2 1 1

【输出样例】

NO YES

【核心思想】

1. 问题分析：给定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​。

2. 算法选择：

   • 并查集（Disjoint Set Union, DSU）：维护变量的等价类，支持O ( α ( n ) ) O(\alpha(n))O(α(n))的合并与查询
   • 离散化（Hash/Map）：变量编号可能很大（达到10 9 10^9109），需要映射为连续的编号
   • 两遍扫描策略：先合并所有相等关系，再检查不等关系是否冲突

3. 关键步骤：

   • 离散化：使用unordered_map将原始变量值x , y x, yx,y映射为1 ∼ n 1 \sim n1∼n的连续编号
   • 初始化并查集：p[i] = i，每个变量初始独立
   • 第一遍：处理相等约束（e = 1 e = 1e=1）：
     • 对于每个相等约束( x i , x j ) (x_i, x_j)(xi​,xj​)：
       • pa = find(x_i),pb = find(x_j)
       • p[pa] = pb：将两个等价类合并
   • 第二遍：检查不等约束（e = 0 e = 0e=0）：
     • 对于每个不等约束( 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

4. 时间/空间复杂度：

   • 时间复杂度：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)，并查集父节点数组和离散化映射表

5. 并查集的核心思想：

   • 等价类维护：将相等的变量归入同一集合，利用路径压缩优化查询效率
   • 传递闭包：相等关系具有传递性，并查集天然支持这种闭包计算
   • 冲突检测策略：必须先处理所有相等关系（建立等价类），再检查不等关系。若顺序颠倒，可能导致错误判断
   • 离散化必要性：当变量范围极大而实际出现次数较少时，通过哈希映射压缩空间
   • 适用于变量分组、连通性判断、等价关系推理类问题

【算法标签】

#并查集

【代码详解】

#include<bits/stdc++.h>usingnamespacestd;constintN=200005;// 最大节点数（离散化后最多 n 个节点）intn,m,T;// n: 离散化后的节点计数, m: 约束条件个数, T: 测试用例数intp[N];// 并查集父节点数组unordered_map<int,int>S;// 离散化映射：原始变量值 -> 连续编号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(){cin>>T;// 读入测试用例数while(T--)// 遍历每个测试用例{n=0;// 重置节点计数器（用于离散化）S.clear();// 清空离散化映射cin>>m;// 读入约束条件个数for(inti=1;i<=m;i++){intx,y,e;cin>>x>>y>>e;// 读入原始变量值和约束类型query[i]={get(x),get(y),e};// 离散化后存入查询数组}for(inti=1;i<=n;i++)p[i]=i;// 初始化并查集：每个节点自成一个集合// 第一遍：处理所有 "相等" 约束（e=1），合并对应集合for(inti=1;i<=m;i++){if(query[i].e==1){intpa=find(query[i].x),pb=find(query[i].y);p[pa]=pb;// 将 x 所在集合的根指向 y 所在集合的根}}// 第二遍：检查所有 "不等" 约束（e=0）是否产生矛盾boolhas_conflict=false;for(inti=1;i<=m;i++){if(query[i].e==0){intpa=find(query[i].x),pb=find(query[i].y);if(pa==pb)// 若原本应不等的两个变量已在同一集合{has_conflict=true;// 发现矛盾，约束不可同时满足break;}}}if(has_conflict)cout<<"NO"<<endl;// 存在矛盾，不可满足elsecout<<"YES"<<endl;// 无矛盾，可以满足}return0;}

【运行结果】

2 2 1 2 1 1 2 0 NO 2 1 2 1 2 1 1 YES