* {'Aplicaţii':2-sat#aplicatii}
** {'Party (preOni 2003/2004)':2-sat#party}
** {'Cigraf':2-sat#cigraf}

** {'Peace Commission':2-sat#peace-commission}

** {'Peace Commission (Polish Olympiad in Informatics, 2001)':2-sat#peace-commission}
** {'Excursion (Baltic Olympiad in Informatics, 2001)':2-sat#excursion}

h2(#introducere). Introducere

Transformăm această problemă într-o instanţă de $2SAT$ astfel: faptul că nodul <tex> x </tex> aparţine mulţimii <tex> C </tex> îl reprezentăm dândui lui <tex> x </tex> valoarea <tex> 1 </tex>, iar apartenenţa mulţimii <tex> I </tex> se codifică prin valoarea <tex> 0 </tex>. Acum existenţa unei muchii <tex> (x, y) </tex> corespunde expresiei <tex> x \vee y </tex>, astfel cel puţin unul din nodurile <tex> x </tex> şi <tex> y </tex> nu va fi în mulţimea <tex> I </tex>. Dacă nu există muchia <tex> (x, y) </tex> putem scrie <tex> \sim x \vee \sim y </tex>, această expresie va fi adevărată dacă cel puţin un nod din cele două nu va fi în mulţimea <tex> C </tex>.
Această soluţie este liniară ca şi complexitate în numărul de elemente citite la intrare.

h2(#peace-commission). Peace Commission (Polish Olympiad in Informatics 2001)

h2(#peace-commission). Peace Commission (Polish Olympiad in Informatics, 2001)

bq. Comisia Publică a Păcii trebuie să fie compusă în parlamentul Republicii Democrate a ţării Byteland după regulile impuse de Legea Foarte Importantă. Din păcate unul dintre obstacole este acela că unii deputaţi nu se înţeleg cu ceilalţi. Comisia trebuie realizată astfel ca următoarele condiţii să fie îndeplinite: fiecare partid trebuie să aibă exact un reprezentant în comisie; dacă doi deputaţi nu se înţeleg, ei nu pot fi ambii membrii ai comisiei. Fiecare partid are exact doi deputaţi în parlament. Toţi număraţi de la $1$ până la $2n (1 <= n <= 8000)$. Deputaţii cu numerele $2i-1$ şi $2i$ aparţin celui de al $i$-lea partid. Se vor da $m (0 <= m <= 20 000)$ perechi de deputaţi <tex> (a, b) </tex> care nu se înţeleg. Se cere realizarea unei comisii dacă acest lucru este posibil. Un exemplu ar fi pentru trei partide şi perechile <tex> (1, 3) </tex> şi <tex> (2, 4) </tex> care nu se înţeleg comisia alcătuită din membrii <tex> \{1, 4, 5\} </tex>.

Exemplu 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 treilea algoritm 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 $2SAT$. 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>.