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.