题解

算法分析

本题是一个典型的 并查集（Disjoint Set Union, DSU） 应用问题，属于 图论 中的 等价关系维护 问题。

问题本质

我们需要处理两种约束：

1. 相等约束（$e=1$）：$x_i = x_j$，表示两个变量必须属于同一个等价类
2. 不等约束（$e=0$）：$x_i \neq x_j$，表示两个变量必须属于不同的等价类

解题思路

1. 离散化处理：由于变量编号范围很大（$1 \leq i,j \leq 10^9$），但实际出现的不同变量数量有限（最多 $2 \times 10^6$），使用哈希表进行离散化映射。

2. 并查集维护相等关系：

   • 初始化每个变量为独立的集合
   • 对于每个相等约束，将两个变量所在的集合合并

3. 检查不等约束：

   • 在所有相等关系处理完成后，检查每个不等约束
   • 如果两个变量在同一个集合中，说明存在矛盾

算法标签

• 并查集（DSU）
• 离散化
• 图论 - 连通分量

代码实现要点

#include <bits/stdc++.h>
using namespace std;

unordered_map<int, int> mp;  // 离散化映射
int p[1000010];             // 并查集数组
pll op[100010];             // 存储不等约束

// 并查集查找
int find(int x) {
    if (p[x] != x) p[x] = find(p[x]);
    return p[x];
}

// 初始化并查集
void init() {
    for (int i = 1; i <= 1000000; i++)
        p[i] = i;
}

时间复杂度

• 离散化：$O(n)$
• 并查集操作：近似 $O(n \cdot \alpha(n))$，其中 $\alpha(n)$ 是反阿克曼函数
• 总体复杂度：$O(n \cdot \alpha(n))$，能够处理 $n \leq 10^6$ 的数据规模

空间复杂度

• $O(n)$，用于存储离散化映射和并查集结构

总结

本题通过并查集高效维护变量间的等价关系，结合离散化处理大范围编号，是并查集的经典应用场景。关键在于先处理所有相等约束建立连通关系，再验证不等约束是否矛盾。