** {'Soluţie $O(M + N)$':2-sat#solutie4}
* {'Aplicaţii':2-sat#aplicatii}
** {'Party (preOni 2003/2004)':2-sat#party}

** {'Cigraf':2-sat#cigraf}

h2(#introducere). Introducere

h2(#cigraf). Cigraf

_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>.
h3. Soluţie