2 SAT

Definition:
(x1 v x2) ^ (x1 v -x2) ^ ....
per clause two literals.

Algorithm to found whether there exits a possible assignment or not?
Build implication graph corresponding and then check whether there exists a path from x to -x or not.
If such path exists, then no valid assignment can be done.

Building implication graph
(x v y) add edge -x to y, and -y to x.

Algorithm to find a possible assignment?

First check for the existence case.
for each unassigned literal x, assign it to true and all the y such x -> y, then assign y to true,
Assign all the opposite of these literals to be false.

Implementation:

Problems to practice:
https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&category=43&page=show_problem&problem=2453
http://www.spoj.com/problems/TORNJEVI/
http://www.spoj.com/problems/SUPSUP/
http://2011.nwerc.eu/results.php (Piece it Together ).
http://2012.nwerc.eu/en/results/problems/

References:
http://users.cms.caltech.edu/~umans/cs21/lec17.pdf
http://kartikkukreja.wordpress.com/2013/05/16/solving-2-sat-in-linear-time/
http://classes.soe.ucsc.edu/cmps132/Winter05/hw/hw8sols.pdf
http://apps.topcoder.com/forums/?module=Thread&threadID=803822&start=0&mc=2