Use a n x n array. initialize with -1 (don't care = no constraints). If there is an equality constraint, set to 1, if explicity non-equality constraint is expected, replace with 0. While doing either of these if you come across a situation where 0 has to be overwritten by 1 or 1 has to be overwritten by 0, the system constraints cannot be satisfied, else all is well. Space required = n^2 bytes. Time complexity = O(c) where c= number of constraints for the system. Therefore, independent of the number of variables.
You can do this with hash tables too and probably save memory. Here you'll use not store = -1 = don't care. -Minotauraus. On Jun 7, 12:16 pm, divya <sweetdivya....@gmail.com> wrote: > 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 input m constraints over n variables and > decides whether the constraints can be satisfied. -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
