Proceed with the above logic of 2D array and only fill the matrix
considering only the equality constraints ( xi=xj)
Using the Floyd warshall All pair shortest path algorithm, we can know the
all reachable places from every other place.
Now fill the matrix as per the inequality constraints(xi!=xj)
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 overw
Your time complexity is not O(c) but O(n^2)
--
--
Rohit Saraf
Second Year Undergraduate,
Dept. of Computer Science and Engineering
IIT Bombay
http://www.cse.iitb.ac.in/~rohitfeb14
--
You received this message because you are subscribed to the Goog
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 overwritt
