** {'Party (preONI 2003/2004)':2-sat#party}
** {'Cigraf':2-sat#cigraf}
** {'Peace Commission (Polish Olympiad in Informatics, 2001)':2-sat#peace-commission}

** {'Excursion (Baltic Olympiad in Informatics, 2001)':2-sat#excursion}

** {'Orpath (Olimpiadă Rusia)':2-sat#orpath}
** {'Aladdin (Bursele Agora 2005/2006, Runda 1)':2-sat#aladdin}
* {'Bibliografie':2-sat#bibliografie}

Exemplul din problemă poate fi scris ca expresia logică în modul următor: <tex> A_{1} \wedge \sim A_{1} \wedge A_{2} \wedge \sim A_{2} \wedge A_{3} \wedge \sim A_{3} \wedge (A_{1} \vee A_{2}) \wedge (\sim A_{1} \vee \sim A_{2}) </tex>.
Din nou vom putea folosi cel de al {'patrulea algoritm':2-sat#solutie4} explicat pentru a obţine o rezolvare de complexitate $O(N + M)$.

h2(#excursion). Excursion (Baltic Olympiad in Informatics, 2001)
 
bq. Un grup de turişti are ocazia să viziteze mai multe oraşe. Fiecare turist spune două dorinţe ale sale despre ce oraş ar vrea sau nu ar vrea să viziteze. O dorinţă a turistului  va spune despre exact un oraş dacă vrea sau nu vrea să îl viziteze. Este posibil ca ambele dorinţe ale unui turist să exprime acelaşi lucru sau să exprime lucruri opuse (de exemplu „Vreau să vizitez oraşul A!” şi „Nu vreau să vizitez oraşul A!”). Va trebui să determinaţi după citirea cerinţelor celor $n$ turişti despre $m$ oraşe dacă există o mulţime a oraşelor pentru care cel puţin o dorinţă a fiecărui turist este îndeplinită $(1 <= n <= 20 000, 1 <= m <= 8 000)$. De exemplu, să presupunem că avem $3$ turişti, $4$ oraşe şi primul turist are dorinţele de a vizita oraşul întâi şi de a nu vizita oraşul doi, al doilea turist are dorinţele de a vizita oraşul doi şi de a vizita oraşul patru, iar al treilea turist are dorinţele de a vizita oraşul trei şi de a vizita oraşul unu. O soluţie pentru acest exemplu ar fi vizitarea tuturor oraşelor.
 
h3. Soluţie
 
Este evident că şi această problemă se poate uşor transforma într-o instanţă de $2-SAT$. Fiecare turist ne dă prin dorinţele sale o expresie literală cu doi literali. Vizitarea sau nevizitarea oraşului de index $i$ va fi reprezentată prin variabila booleană <tex> A_{i} </tex>.  Exemplul din problemă poate fi transformat astfel: <tex> (A_{1} \vee \sim A_{2}) \wedge (A_{2} \vee A_{4}) \wedge (A_{3} \vee A_{1}) </tex>.
 

h2(#orpath). Orpath (Olimpiadă Rusia)
bq. Într-o ţară pacifistă, există $N$ oraşe şi $K$ autobuze $(1 <= N, K <= 100)$. La orele aglomerate ale zilei, nu trebuie să existe două autobuze care merg în acelaşi timp în sensuri opuse. Traseul fiecărui autobuz este un ciclu. Spunem că el merge în sens pozitiv dacă va parcurge oraşele în ordinea $1 2 3 4 1 2 3 4 1 2$ ... sau în sens negativ dacă le parcurge în ordinea $1 4 3 2 1 4 3 2 1 4$ ... Găsiţi o posibilitate de atribuire a sensului fiecărui autobuz astfel ca accidentele de trafic să fie evitate (nu vor exista două autobuze care să se întâlnească şi să aibă sensuri de mers opuse). Pentru fiecare autobuz se vor şti oraşele de pe ruta lui, şi pentru fiecare două oraşe vecine pe rută se va şti timpul necesar autobuzului pentru a ajunge dintr-un oraş în altul. De exemplu, pentru $4$ oraşe unde oricare două sunt la timp de mers egal cu $10$, şi pentru două autobuze cu rutele $1 2 4$ şi $3 4 2$, o soluţie ar fi ca primul autobuz să meargă în sens pozitiv iar celălalt în sens negativ.