Satisfiability of Equality Equations
Determine whether equality and inequality equations can all be satisfied.
Pattern fit
Union equal variables first, then verify that no inequality tries to separate variables that already belong to the same component.
Key observation
Equalities build components; inequalities validate whether the built components are consistent.
Target complexity
O(n alpha(n)) / O(1)
How to break down the solution cleanly
Union equal variables first, then verify that no inequality tries to separate variables that already belong to the same component.
Equalities build components; inequalities validate whether the built components are consistent.
Initialize each node as its own parent.
Compress paths during find so future queries stay cheap.
Reference implementation
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
Common pitfalls
Checking equalities and inequalities in one mixed pass.
Forgetting that all equalities should be processed before any inequality checks.
Common follow-ups
Why must equalities be processed first?
How does this change with more than 26 variables?
Continue with related problems
Build repeatable depth inside the Union Find cluster before moving on.