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 dis equality constraints, of the form
xi != xj Is it possible to satisfy all of them? Give an efficient
algorithm that takes as
A simple solution :
Use the union find data structure and add notes for x1...xn and the negation
of all these.
Every constraint makes one union.
Finally check if for any i , xi and !xi are connected.
It is worst case O(n lg n) for sure where n is the number of equations.
Average case is much
