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 better. -------------------------------------------------- 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 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.