题目定位
先把等式变量统一归并，再检查是否有不等式要求把同一连通块里的变量分开。
关键观察
等式负责构造连通块，不等式负责验证这些连通块是否自洽。
目标复杂度
O(n alpha(n)) / O(1)
这题的解法思路怎么拆
1
先把等式变量统一归并，再检查是否有不等式要求把同一连通块里的变量分开。
2
等式负责构造连通块，不等式负责验证这些连通块是否自洽。
3
初始化时每个节点都是自己的父节点。
4
find 时做路径压缩，保证后续查询足够快。
参考实现
Python# Generic pattern template
class UnionFind:
def __init__(self, n):
self.parent = list(range(n))
self.rank = [0] * n
def find(self, x):
if self.parent[x] != x:
self.parent[x] = self.find(self.parent[x])
return self.parent[x]
def union(self, a, b):
pa, pb = self.find(a), self.find(b)
if pa == pb:
return False
if self.rank[pa] < self.rank[pb]:
pa, pb = pb, pa
self.parent[pb] = pa
if self.rank[pa] == self.rank[pb]:
self.rank[pa] += 1
return True
常见坑点
warning
把等式和不等式混在一轮里处理。
warning
忘了必须先处理完全部等式，再检查不等式。
高频追问
为什么必须先处理等式？
如果变量数量远大于 26，该怎么扩展？
继续刷相关题
先把 并查集 这个模式刷成体系，再去做更难变体。