Here's a problem that occurs in automatic program analysis. for a set of variables x1; : : : ; xn, you are given some equality constraints, of the form xi = xj and some disequality constraints,
of the form xi 6= xj . is it possible to satisfy all of them?
for instance, the constraints
x1 = x2; x2 = x3; x3 = x4; x1 6= x4
cannot be satis ed. give an ef cient algorithm that takes as input mconstraints over n variables
and decides whether the constraints can be satisfied.