Nu aveti permisiuni pentru a descarca fisierul grader_test2.in
Diferente pentru problema/2sat intre reviziile #27 si #28
Nu exista diferente intre titluri.
Diferente intre continut:
O alta solutie neoptima, in complexitatea $O(N^2^)$ se bazeaza pe un algoritm randomizat. Initial se atribuie valori arbitrare variabilelor, iar apoi cat timp expresia nu este satisfacuta se gaseste o propozitie cu valoarea de adevar $0$ si se schimba valoarea unuia dintre cei 2 termeni componenti ai propozitiei.
Solutia optima, in complexitatea $O(M + N)$ se foloseste de relatia de implicatie, transformand astfel problema intr-una de grafuri, care se poate rezolva determinand compomentele tare-conexe.
Solutia optima, in complexitatea $O(M + N)$ se foloseste de relatia de implicatie, transformand astfel problema intr-una de grafuri, care se poate rezolva determinand 'compomentele tare-conexe':/problema/ctc.
Pentru mai multe detalii in legatura cu solutiile consultati 'articolul':/2-sat.
