Greedy Algorithms

Here$$s a problem that occurs in automatic program analysis. For a set of variables x$1,...,$ xn$,$ you

are given some equality constraints, of the form $$xi $=$ xj$$ and some disequality constraints, of the

form $$xi $!=$ xj$.$ Is it possible to satisfy all of them?

For instance, the constraints

x$1=$ x$2,$ x$2=$ x$3,$ x$3=$ x$4,$ x$1!=$ x$4$

cannot be satisfied.

$($a$)$ Give an efficient algorithm that takes as input m constraints over n variables and decides

whether the constraints can be satisfied.

Hint: One possible option is to consider a graph