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

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 satisfied. give an efficient algorithm that takes as input m constraints over n variables and decides whether the constraints can be satisfied.