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.