The following problem is an application from automated program analysis. For a set of variables x1..... xn, you are given some equality constraints, of the form xi = xj and some inequality 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, and x1 6= x4 cannot be satis fied.
Give an efficient algorithm that takes as input m constraints over n variables and decides whether the constraints can be satis fied.