Dacă avem <tex> A \longrightarrow B </tex> o muchie în graful nostru şi literalul <tex> A </tex> este adevărat, atunci şi literalul <tex> B </tex> trebuie să fie adevărat pentru ca propoziţia reprezentată de muchie să fie satisfăcută. Putem demonstra prin inducţie că dacă există un drum în graf de la literalul <tex> A </tex> la literalul <tex> B </tex>, atunci dacă <tex> A </tex> este adevărat şi <tex> B </tex> trebuie să fie adevărat. Dacă există un drum de la un literal <tex> X </tex> la <tex> \sim X </tex>, precum şi un drum invers, atunci nu va exista soluţie pentru că nu putem seta în acelaşi timp o variabilă şi valoarea ei negată la valoarea adevărat. De aici rezultă că dacă în graful asociat expresiei există o variabilă <tex> X </tex> în aceeaşi componentă tare conexă cu <tex> \sim X </tex> atunci instanţa problemei satisfiabilităţii nu poate fi satisfăcută. Dacă nu există o asemenea variabilă, vom vedea în continuare cum putem rezolva problema. Întâi, facem observaţia că dacă în graf există muchia <tex> A \longrightarrow B </tex> atunci există şi muchia <tex> \sim B \longrightarrow \sim A </tex>. Astfel, dacă există un drum de la <tex> A </tex> la <tex> B </tex> în graf, aplicând proprietatea menţionată pentru fiecare muchie a drumului, vom găsi un drum de la <tex> \sim B </tex> la <tex> \sim A </tex>. Evident, afirmaţia este valabilă şi reciproc: dacă există drum de la <tex> B </tex> la <tex> A </tex> atunci vom avea un drum de la nodul <tex> \sim A </tex> la <tex> \sim B </tex>. Astfel, dacă avem că <tex> A </tex> şi <tex> B </tex> sunt în aceeaşi componentă tare conexă atunci şi nodurile <tex> \sim A </tex> şi <tex> \sim B </tex> sunt în aceeaşi componentă tare conexă. Deci, dacă nu există doi literali <tex> X </tex> şi <tex> \sim X </tex> în aceeaşi componentă tare conexă, putem să împărţim graful în componente tare conexe şi să împerechem componentele câte două astfel ca în fiecare pereche să apară o componentă <tex> U </tex> cu nişte literali şi altă componentă <tex> \sim U </tex> cu aceiaşi literali negaţi. Pentru a găsi o soluţie vom determina mai întâi componentele tare conexe ale grafului. Apoi putem contracta fiecare componentă într-un nod. Graful obţinut va fi aciclic. Alegem un nod <tex> u </tex> în care nu intră nicio muchie (un asemenea nod trebuie să existe pentru a nu exista cicluri). Din considerente de simetrie, din nodul lui pereche <tex> \sim u </tex> nu va ieşi nicio muchie. Literalilor componentei <tex> U </tex> putem să le dăm valoarea de adevăr <tex> 0 </tex>, iar literalilor din componenta pereche <tex> \sim U </tex>  putem să le dăm valoarea de adevăr <tex> 1 </tex>. Această alegere nu impune restricţii asupra celorlalţi literali şi elimină câteva variabile din problemă. Repetarea recursivă a acestui pas pe graful rămas va duce la rezolvarea problemei. Determinarea componentelor tare conexe se poate face în complexitatea $O(N + M)$. Pentru a vedea acest algoritm puteţi consulta 'secţiunea $23.5$':http://zhuzeyuan.hp.infoseek.co.jp/ita/chap23.htm din {'[1]':2-sat#bibliografie}. Iar eliminarea nodurilor de care vorbeam mai sus se poate face în $O(N + M)$ folosind o sortare topologică.

Să urmărim cum merge algoritmul nostru pe exemplul de mai sus. Componentele tare conexe sunt următoarele: <tex> \{A\} </tex>, <tex> \{\sim A\} </tex>, <tex> \{B, C, \sim D\} </tex>, <tex> \{\sim B, \sim C, D\} </tex>. În nodul asociat componentei <tex> \{A\} </tex> nu intră nici o muchie. Astfel, putem să îi atribuim lui <tex> A </tex> valoarea <tex> 0 </tex>, iar după eliminarea lui <tex> \{A\} </tex> şi <tex> \{\sim A\} </tex>în nodul asociat componentei <tex> \{\sim B, \sim C, D\} </tex> nu intră nicio muchie, deci putem să îi atribuim lui <tex> B </tex> valoarea <tex> 1 </tex>, lui <tex> C </tex> valoarea <tex> 1 </tex> şi lui <tex> D </tex> valoarea <tex> 0 </tex>. Această atribuire este satisfiabilă după cum vedem în continuare:

Să urmărim cum merge algoritmul nostru pe exemplul de mai sus. Componentele tare conexe sunt următoarele: <tex> \{A\} </tex>, <tex> \{\sim A\} </tex>, <tex> \{B, C, \sim D\} </tex>, <tex> \{\sim B, \sim C, D\} </tex>. În nodul asociat componentei <tex> \{A\} </tex> nu intră nicio muchie. Astfel, putem să îi atribuim lui <tex> A </tex> valoarea <tex> 0 </tex>, iar după eliminarea lui <tex> \{A\} </tex> şi <tex> \{\sim A\} </tex>în nodul asociat componentei <tex> \{\sim B, \sim C, D\} </tex> nu intră nicio muchie, deci putem să îi atribuim lui <tex> B </tex> valoarea <tex> 1 </tex>, lui <tex> C </tex> valoarea <tex> 1 </tex> şi lui <tex> D </tex> valoarea <tex> 0 </tex>. Această atribuire este satisfiabilă după cum vedem în continuare:

<tex> (\sim A \vee \sim B) \wedge (B \vee \sim C) \wedge (B \vee C) \wedge (\sim B \vee \sim D) \wedge (C \vee D) = </tex> <tex> (\sim 0 \vee \sim 1) \wedge (1 \vee \sim 1) \wedge (1 \vee 1) \wedge (\sim 1 \vee \sim 0) \wedge (1 \vee 0) = </tex> <tex> 1 \wedge 1 \wedge 1 \wedge 1 \wedge 1 = 1 </tex>

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!

bq. George vrea să îşi organizeze majoratul şi îşi doreşte 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 preferinţe 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 identificaţ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ă nicio 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!

h3. Soluţie

Această problemă este inspirită din o problemă de la $CEOI 2002$ şi este evident că ne cere să determinăm o atribuire satisfiabilă pentru o formulă logică formată ca conjuncţie între cerinţele care se transformă astfel:

Această problemă este inspirată dintr-o problemă de la $CEOI 2002$ şi este evident că ne cere să determinăm o atribuire satisfiabilă pentru o formulă logică formată ca conjuncţie între cerinţele care se transformă astfel:

* _cerinţa de tip 0_ corespunde propoziţiei <tex> x \vee y </tex>;
* _cerinţa de tip 1_ corespunde propoziţiei <tex> x \vee \sim y </tex>;

_Autor: Mugurel Ionuţ Andreica_

bq. Se dă un graf neorientat cu $N (1 <= N <= 1000)$ noduri şi $M (0 <= M <= N*(N-1)/2)$ muchii. Se doreşte împărţirea nodurilor acestui graf în $2$ mulţimi, <tex> C </tex> şi <tex> I </tex>, având următoarele proprietăţi: fiecare nod face parte din exact una din cele $2$ mulţimi, există muchie între oricare $2$ noduri din mulţimea <tex> C </tex>, nu există nicio muchie între $2$ noduri din mulţimea <tex> I </tex>. Este posibil ca una dintre cele $2$ mulţimi să fie vidă. Soluţia nu este neaparat unică. Numele celor două mulţimi provin de la $clică$ şi $mulţime independentă$. De exemplu, pentru graful de $6$ noduri ce are muchiile <tex> \{\{1, 4\}, \{4, 6\}, \{6, 1\}, \{2, 4\}, \{2, 6\}, \{3, 4\}, \{1, 3\}\} </tex> o împărţire posibilă ar fi <tex> C = \{1, 4, 6\} </tex>, <tex> I = \{2, 3, 5\} </tex>.

bq. Se dă un graf neorientat cu $N$ ({$1 &le; N &le; 1000$}) noduri şi $M$ ({$0 &le; M &le; N*(N-1)/2$}) muchii. Se doreşte împărţirea nodurilor acestui graf în $2$ mulţimi, <tex> C </tex> şi <tex> I </tex>, având următoarele proprietăţi: fiecare nod face parte din exact una din cele $2$ mulţimi, există muchie între oricare $2$ noduri din mulţimea <tex> C </tex>, nu există nicio muchie între $2$ noduri din mulţimea <tex> I </tex>. Este posibil ca una dintre cele $2$ mulţimi să fie vidă. Soluţia nu este neapărat unică. Numele celor două mulţimi provin de la $clică$ şi $mulţime independentă$. De exemplu, pentru graful de $6$ noduri ce are muchiile <tex> \{\{1, 4\}, \{4, 6\}, \{6, 1\}, \{2, 4\}, \{2, 6\}, \{3, 4\}, \{1, 3\}\} </tex> o împărţire posibilă ar fi <tex> C = \{1, 4, 6\} </tex>, <tex> I = \{2, 3, 5\} </tex>.

h3. Soluţie

Dacă între două noduri există muchie atunci nu pot fi amândouă în mulţimea <tex> I </tex>, iar dacă între două noduri nu există muchie nu pot fi amândouă în mulţimea <tex> C </tex>.
Transformăm această problemă într-o instanţă de $2-SAT$ 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.

Dacă între două noduri există muchie atunci nu pot fi amândouă în mulţimea <tex> I </tex>, iar dacă între două noduri nu există muchie nu pot fi amândouă în mulţimea <tex> C </tex>. Transformăm această problemă într-o instanţă de $2-SAT$ astfel: faptul că nodul <tex> x </tex> aparţine mulţimii <tex> C </tex> îl reprezentăm dându-i lui <tex> x </tex> valoarea <tex> 1 </tex>, iar apartenenţa la mulţimea <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)

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>.

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 &le; n &le; 8000)$. Deputaţii cu numerele $2i-1$ şi $2i$ aparţin celui de al $i$-lea partid. Se vor da $m (0 &le; m &le; 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>.

h3. Soluţie

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.

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.

h3. Soluţie

h2(#aladdin). 'Aladdin':problema/aladdin (Bursele Agora 2005/2006, Runda 1)

bq. Aladdin, aşa cum ştiaţi, este un mare magnat în afacerea de comercializare a covoarelor magice. Acesta doreşte să o cucerească pe prinţesa Iasmina, iar aceasta, pentru a-i testa inteligenţa îl roagă să îi facă un covor dreptunghiular împărţit în pătrăţele, asemănator unei table de şah cu $N$ linii şi $M$ coloane $(1 <= N, M <= 1000)$. Fiecare pătrăţel de pe covor trebuie colorat cu alb sau cu negru. Pentru fiecare pătrat care conţine $4$ pătrăţele Iasmina pune condiţia să aibă un număr fixat de pătrăţele colorate cu negru. Ajutaţi-l pe Aladdin să realizeze un covor care satisface condiţiile impuse de prinţesa Iasmina!

bq. Aladdin, aşa cum ştiaţi, este un mare magnat în afacerea de comercializare a covoarelor magice. Acesta doreşte să o cucerească pe prinţesa Iasmina, iar aceasta, pentru a-i testa inteligenţa îl roagă să îi facă un covor dreptunghiular împărţit în pătrăţele, asemănator unei table de şah cu $N$ linii şi $M$ coloane $(1 ≤ N, M ≤ 1000)$. Fiecare pătrăţel de pe covor trebuie colorat cu alb sau cu negru. Pentru fiecare pătrat care conţine $4$ pătrăţele Iasmina pune condiţia să aibă un număr fixat de pătrăţele colorate cu negru. Ajutaţi-l pe Aladdin să realizeze un covor care satisface condiţiile impuse de prinţesa Iasmina!

h3. Soluţie

<tex> 0 \le y_{2} \le 1,  0 \le  x_{1} - y_{2} \le  1,-1 \le  x_{2} + y_{2} \le 0,  1 \le  x_{3} - y_{2} \le  2, </tex>
<tex> 0 \le y_{3} \le 1, -1 \le -x_{1} - y_{3} \le  0, 0 \le -x_{2} + y_{3} \le 1, -1 \le -x_{3} - y_{3} \le  0 </tex>

Transformăm relaţiile astfel ca să nu apară nici o constantă negativă:

Transformăm relaţiile astfel ca să nu apară nicio constantă negativă:

<tex> 0 \le x_{1} \le 1, 0 \le x_{2} \le 1, 0 \le x_{3} \le  1, </tex>
<tex> 0 \le y_{1} \le 1, 1 \le x_{1} + y_{1} \le 2, 0 \le -x_{2} + y_{1} \le 1, 2 \le x_{3} + y_{1} \le 3, </tex>