Using an n*n array, am afraid, will not solve the problem, since its not capable to capture transitivity.
Consider the case: v1=v2 v3=v2 v3!=v1 we will place 0 in arr(1,2) arr(2,1) for v1=v2 we will place 0 in arr(2,3) arr(3,2) for v3=v2 and place 1 in arr(1,3) and arr(3,1) for v3!=v1. no overwrite :( and still the constraints cannot be satisfied. -jkd On Tue, Jun 8, 2010 at 10:07 PM, Minotauraus <[email protected]> wrote: > 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 <[email protected]> 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 [email protected]. > To unsubscribe from this group, send email to > [email protected]<algogeeks%[email protected]> > . > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > > -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
