问题分析

本题是一道基于并查集（Union-Find） 的逻辑约束判定问题，核心任务是处理一系列逻辑关系操作后，统计处于"不确定"状态的变量数量。每个变量可处于三种状态：真（T）、假（F）或不确定（U），通过特定操作建立变量间的逻辑关系。

算法思路

1. 状态表示与映射

• 定义三种特殊状态：
  • T（真）：映射为 $N + 1$（$N$ 为变量最大数量，避免与普通变量冲突）
  • F（假）：映射为 $-N - 1$
  • U（不确定）：映射为 $0$
• 普通变量 $i$ 的否定状态表示为 $-i$，用于表达"变量 $i$ 为假"的逻辑。

2. 并查集的扩展应用

• 使用数组 f[i] 存储变量 $i$ 的逻辑关联：
  • f[i] = j 表示 $i$ 与 $j$ 等价（$i$ 为真 $\iff$ $j$ 为真）
  • f[i] = -j 表示 $i$ 与 $j$ 对立（$i$ 为真 $\iff$ $j$ 为假）
• 通过 find 函数递归查找变量的最终状态，处理传递性逻辑关系：
  • 若变量 $i$ 关联到 $j$，则 $i$ 的状态由 $j$ 的状态决定
  • 若变量 $i$ 关联到 $-j$，则 $i$ 的状态与 $j$ 的状态相反

3. 操作处理

支持三种操作：

1. + i j：建立等价关系 $i \iff j$，即 f[i] = f[j]
2. - i j：建立对立关系 $i \iff \neg j$，即 f[i] = -f[j]
3. T/F/U i：直接设置变量 $i$ 的状态为真/假/不确定，即 f[i] = 映射值

4. 状态判定

• 对每个变量 $i$，调用 find(i) 确定其最终状态：
  • 若返回 $0$：变量处于不确定状态
  • 若返回 $N + 1$：变量为真
  • 若返回 $-N - 1$：变量为假
• 统计返回 $0$ 的变量数量，即为答案。

5. 递归与环检测

find 函数中使用 vis 数组标记递归路径，避免无限循环（处理逻辑环）：

• 若递归中遇到已访问的变量，说明存在逻辑环
• 逻辑环会导致变量状态无法确定（返回 $0$）

关键公式与复杂度

1. 状态映射：

   • $T \rightarrow N + 1$
   • $F \rightarrow -N - 1$
   • $U \rightarrow 0$ 该映射确保特殊状态与普通变量不冲突。

2. 逻辑关系：

   • 等价关系：$f[i] = f[j] \implies i \iff j$
   • 对立关系：$f[i] = -f[j] \implies i \iff \neg j$

3. 时间复杂度：

   • 每个 find 操作的递归深度取决于逻辑关系的传递链，平均复杂度接近 $O(1)$（路径压缩效应）
   • 处理 $m$ 次操作和 $n$ 个变量的总复杂度为 $O((n + m) \alpha(n))$，其中 $\alpha$ 是阿克曼函数的反函数（增长极慢，可视为常数）
   • 适合处理 $n, m \leq 10^5$ 的数据规模

代码解析

算法的核心是通过扩展并查集表达复杂的逻辑关系，利用递归处理传递性约束，同时通过访问标记避免逻辑环导致的无限循环，高效解决了逻辑状态判定问题。