** {'Soluţie $O(N^2^)$':2-sat#solutie-3}
** {'Soluţie $O(M + N)$':2-sat#solutie-4}
* {'Aplicaţii':2-sat#aplicatii}

** {'Party (preOni 2003/2004)':2-sat#party}

** {'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}

Restul articolului va prezenta aplicaţii ale problemei $2-SAT$ la concursurile de programare.

h2(#party). 'Party':problema/party (preOni 2003/2004)

h2(#party). 'Party':problema/party (preONI 2003/2004)

bq. George vrea să îşi organizeze majoratul, şi vrea ca petrecerea să fie de neuitat, mâncarea, băutura, locaţia şi sonorizarea sunt deja asigurate, mai rămâne problema chemării prietenilor. El şi cu prietenul lui cel mai bun Lucian au preferinte diferite şi pentru a nu se certa au pus la punct o listă de cerinţe care vor trebui să fie îndeplinite astfel încât cheful să se desfăşoare în cele mai bune condiţii! Pentru uşurinţă,  prietenii lui George vor fi indentificaţi prin numere întregi de la $1$ la $N (1 ≤ N ≤ 100)$ şi cerinţele în număr de $M  (1 ≤ M ≤ 1.000)$ vor fi de tipurile 0, 1, 2 sau 3. O cerinţă de genul <tex> x \ y </tex> 0 are semnificaţia că <tex> x </tex> sau <tex> y </tex> trebuie să participe la petrecere; <tex> x \ y </tex> 1 are semnificaţia că dacă <tex> x </tex> participă nu există nici o restricţie pentru <tex> y </tex>, dar dacă <tex> x </tex> nu participă atunci nici <tex> y </tex> nu participa; <tex> x \ y </tex> 2 are semnificaţia simetrică cu cerinţa 1; iar cerinţa <tex> x \ y </tex> 3 are semnificaţia că cel puţin unul dintre <tex> x </tex> şi <tex> y </tex> nu participă la petrecere. Scrieţi un program care să-i ajute pe cei doi să determine care persoane vor fi invitate la petrecere. Se garantează că va fi posibilă întotdeauna organizarea unei petreceri!