Una din primele două rezolvări ar fi putut soluţiona această problemă, dar problema de la $CEOI$ avea limite mai mari şi pentru rezolvarea ei ar fi trebuit un algoritm de complexitate $O(N + M)$.

h2(#cigraf). Cigraf
 
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
 
Dacă între două noduri există muchie atunci nu pot fi amândouă în mulţimea $I$, iar dacă între două noduri nu există muchie nu pot fi amândouă în mulţimea $C$.
Transformăm această problemă într-o instanţă de $2SAT$ astfel: faptul că nodul <tex> x </tex> aparţine mulţimii $C$ îl reprezentăm dândui lui <tex> x </tex> valoarea <tex> 1 </tex>, iar apartenenţa mulţimii $I$ 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 $I$. 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 $C$.
Această soluţie este liniară ca şi complexitate în numărul de elemente citite la intrare.