Greedy Algorithms $(20$ marks$)$

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 representation of this problem where

each node is a variable $($e$.$g$.$ xi$)$ and an edge represents an $$equality constraint$.$

$($b$)$ Argue $($or do a proof sketch$)$ that your algorithm is correct.

$($c$)$ State the asymptotic cost of your algorithm and justify why it$$s correct.