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 x ₁ = x ₂ ; x ₂ = x ₃ ; x ₃ = x ₄ ; x ₁ 6= x ₄ cannot be satisfied. Give an efficient algorithm that takes as input m constraints over n variables and decides whether the constraints can be satisfied.