2-SAT

Problems on 2-satisfiability, including choosing one of two options for every object under pairwise constraints, assigning people to two groups, and deciding whether a set of boolean clauses with two literals each can be satisfied.

The usual method builds an implication graph and finds its strongly connected components. Related problem sets are under Graphs and Depth-first search.