[NOI2015] 程序自动分析

GitHub跳转原题关系图返回列表

先用字典并查集合并所有相等约束，再检查每条不等约束的两端是否落在同一集合。

OJ: luogu

题目 ID: P1955

难度:普及+/提高

标签:并查集离散化python

日期: 2026-07-16 17:48

目录

  1. 题意
  2. 思路
  3. Python 知识
  4. 代码
  5. 复杂度
  6. 总结

题意

判断若干形如 xi=xjx_i=x_j、xi≠xjx_i\ne x_j 的约束能否同时成立。

思路

相等关系具有传递性，先把所有相等约束放进并查集。随后逐条检查不等约束：若两端已经属于同一集合，就产生矛盾。

变量编号可达 10910^9，但实际只出现 O(n)O(n) 个。Python 可以直接用 dict 以原编号为键，相当于把离散化和并查集存储合在一起。

Python 知识

  • 字典推导式从约束中收集实际出现的变量，参见 /home/rainboy/mycode/hugo-blog/content/program_language/python/dict_usage.md。
  • all(...) 会在第一个矛盾处短路，不会继续做无用检查。
  • dict.fromkeys(parent, 1) 为所有根初始化集合大小。

代码

python
import sys


data = iter(map(int, sys.stdin.buffer.read().split()))
answers = []

for _ in range(next(data)):
    constraints = [(next(data), next(data), next(data)) for _ in range(next(data))]
    parent = {x: x for constraint in constraints for x in constraint[:2]}
    size = dict.fromkeys(parent, 1)

    def find(x):
        while parent[x] != x:
            parent[x] = parent[parent[x]]
            x = parent[x]
        return x

    def union(x, y):
        x, y = find(x), find(y)
        if x == y:
            return
        if size[x] < size[y]:
            x, y = y, x
        parent[y] = x
        size[x] += size[y]

    for x, y, equal in constraints:
        if equal:
            union(x, y)

    answers.append("YES" if all(
        equal or find(x) != find(y) for x, y, equal in constraints
    ) else "NO")

print("\n".join(answers))

复杂度

设约束数为 nn，时间复杂度 O(nα(n))O(n\alpha(n))，空间复杂度 O(n)O(n)。

总结

先处理“必须相等”，再验证“必须不等”，即可把约束满足转成并查集判冲突。