洛谷 P1955 程序自动分析 - Solution

1. 题目数据 (Problem Metadata)

题目类型：传统题
题目链接：P1955 [NOI2015] 程序自动分析 - 洛谷
时间限制：2.00s
内存限制：512.00MB

2. 题意简述 (Problem Summary)

给定 $t$ 个相互独立的约束满足问题。每个问题包含 $n$ 条形如 $(i, j, e)$ 的约束： $e = 1$ 表示 $x_i = x_j$ ， $e = 0$ 表示 $x_i \neq x_j$ 。变量编号 $i, j$ 的范围为 $1 \le i, j \le 10^9$ 。对每个问题，判断是否存在一种变量赋值，使得所有约束同时满足。

输入： $t$ （ $1 \le t \le 10$ ），随后每组数据 $n$ （ $1 \le n \le 10^5$ ）及 $n$ 条约束。
输出：对每组数据输出一行，YES 表示可满足，NO 表示不可满足。

3. 朴素解法 (Brute-Force)

最直接的想法是枚举所有变量的赋值。但变量编号可达 $10^9$ ，且约束数 $n$ 最大为 $10^5$ ，变量个数最多可达 $2 \times 10^5$ ，完全枚举不可行。

另一种思路是建立约束图，用 DFS 染色检测相等关系的连通性，再逐一检查不等关系。但变量编号过大，无法直接开数组建图，且需要处理传递性，实现起来并不比并查集更简单。

4. 核心解法 (Main Solution)

特殊性质

相等关系具有传递性：若 $x_i = x_j$ 且 $x_j = x_k$ ，则必有 $x_i = x_k$ 。因此，所有相等的变量在逻辑上属于同一个等价类。不等关系则要求两个变量必须落在不同的等价类中。

关键突破

利用传递性，我们可以先用并查集（Union-Find）把所有相等约束合并，再逐一检查不等约束。若某条不等约束的两个变量已被合并到同一集合，则矛盾出现，问题不可满足。

变量编号 $i, j$ 最大为 $10^9$ ，无法直接作为并查集数组下标，因此需要离散化：收集每组数据中出现过的所有编号，排序后映射为 $0 \sim m-1$ （或 $1 \sim m$ ），其中 $m \le 2n$ 。

推导过程

算法流程如下：

收集与离散化：读入所有约束，将出现的 $i, j$ 存入数组，排序去重后建立映射 $\text{id}[x]$ 。
合并相等关系：遍历所有 $e = 1$ 的约束，将 $\text{id}[i]$ 与 $\text{id}[j]$ 合并。
检查不等关系：遍历所有 $e = 0$ 的约束，若 $\text{find}(\text{id}[i]) = \text{find}(\text{id}[j])$ ，则矛盾，输出 NO。
若所有不等约束均不矛盾，输出 YES。

下面我们证明这个流程的正确性。

5. 正确性证明 (Proof of Correctness)

引理 1（并查集合并的正确性）：若 $x_i = x_j$ ，则经过并查集合并后， $x_i$ 与 $x_j$ 属于同一集合。并查集的合并操作满足等价关系的自反性、对称性和传递性，因此所有通过相等关系传递可达的变量最终都会被合并到同一集合。

引理 2（检查的充分性）：若存在 $e = 0$ 的约束 $x_i \neq x_j$ ，但 $\text{find}(\text{id}[i]) = \text{find}(\text{id}[j])$ ，则问题无解。因为并查集合并了所有相等关系，若 $x_i$ 与 $x_j$ 在同一集合，说明 $x_i = x_j$ 可由已有相等约束推导得出，与 $x_i \neq x_j$ 矛盾。

定理（算法正确）：上述算法输出 YES 当且仅当约束可满足。

证明：若算法输出 NO，则由引理 2 可知存在矛盾，故不可满足。若算法输出 YES，则所有不等约束的两个变量均在不同集合。此时为每个集合分配一个唯一值（如集合的根节点编号），相等约束因同集合而自动满足，不等约束因不同集合而自动满足。因此存在可行赋值，约束可满足。综上所述，算法正确。

6. 复杂度分析 (Complexity)

时间复杂度： $O(n \log n)$ 。每组数据中，离散化排序 $O(n \log n)$ ，并查集操作 $O(n \alpha(m))$ ，其中 $\alpha$ 为反阿克曼函数，可视为常数。 $n \le 10^5$ 时， $n \log n \approx 1.7 \times 10^6$ ，2s 内可轻松通过。
空间复杂度： $O(n)$ 。离散化数组与并查集数组各 $O(n)$ ，总空间约几 MB，远低于 512 MB 限制。所以数组略微开大一点也没关系。

7. 实现细节与避坑指南 (Implementation Details)

坑点	说明
离散化映射	变量编号最大 $10^9$ ，必须离散化。收集时去重，映射时用 `lower_bound` 或哈希表。 $m \le 2n$ 。
多组数据清空	$t \le 10$ ，每组数据独立。离散化数组、并查集父数组、约束存储数组均需在每组数据开始时重新初始化。
合并顺序	必须先合并所有相等关系，再检查不等关系。若先检查不等关系，会漏掉经由相等传递才产生的矛盾。
数组下标	离散化后下标从 $0$ 或 $1$ 开始均可，但并查集数组大小要相应调整开大一点（约两倍），避免越界。

8. 参考代码 (Reference Code)

#include <iostream>
#include <algorithm>
using namespace std;

const int MAXN = 1e6 + 5;  // 保险起见，直接开十倍

int t, n;
int fa[MAXN];

// z = 1 对应相等约束，存入 i1/j1，计数 a1
// z = 0 对应不等约束，存入 i0/j0，计数 a0
int i1[MAXN], j1[MAXN], a1;
int i0[MAXN], j0[MAXN], a0;
int a[MAXN], b[MAXN], m;

int get(int x)
{
    return fa[x] == x ? x : fa[x] = get(fa[x]);
}

int query(int x) // 离散化：把变量值映射为下标
{
    return lower_bound(b, b + m, x) - b;
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> t; // 多组测试数据
    while (t--)
    {
        cin >> n;
        m = a1 = a0 = 0; // 百年 OI 一场空，不清多测见祖宗
        for (int i = 1; i <= 2 * n; i++)
            fa[i] = i;
        for (int i = 1; i <= n; i++)
        {
            int x, y, z;
            cin >> x >> y >> z;
            if (z == 0)
            {
                a0++;
                i0[a0] = x;
                j0[a0] = y;
            }
            if (z == 1)
            {
                a1++;
                i1[a1] = x;
                j1[a1] = y;
            }
            a[2 * i - 1] = x;
            a[2 * i] = y;
        }
        sort(a + 1, a + 1 + 2 * n);
        for (int i = 1; i <= 2 * n; i++)
        {
            if (i == 1 || a[i] != a[i - 1])
                b[++m] = a[i];
        }

        // 先合并相等关系（a1 中存储的是 z=1 的约束）
        for (int i = 1; i <= a1; i++)
            fa[get(query(i1[i]))] = get(query(j1[i]));

        // 再检查不等关系（a0 中存储的是 z=0 的约束）
        bool flag = 1;
        for (int i = 1; i <= a0 && flag; i++)
            flag &= (get(query(i0[i])) != get(query(j0[i])));

        cout << (flag ? "YES" : "NO") << '\n';
    }
    return 0;
}

9. 补充说明 (Additional Notes)

本题是约束满足问题（Constraint Satisfaction Problem, CSP）的最简形式，只含相等与不等两类二元约束。更一般的 CSP 允许任意定义域与任意关系约束，通常是 NP-Complete 的；但本题由于约束结构极简单，仅靠并查集的合并与查找即可在多项式时间内判定。
若把"相等"视为无向边、"不等"视为不能连通的判定，这题本质上是在问：由相等关系生成的等价类图，是否与不等关系冲突。这个视角也可以扩展到带权约束（如 $x_i - x_j \ge c$ ）或多元约束，那时需要改用带权并查集、差分约束或 SAT 求解器。
若约束中还包含 $x_i < x_j$ 等偏序关系，则需要更复杂的数据结构（如带权并查集），但本题无需考虑。

其他版本

本题的写法有很多变体。一种常见的写法是用结构体数组存储所有约束，读入时统一离散化，再分两遍处理。时间复杂度和空间复杂度与上述版本相同。