×

# Two Sat Problem

 0 Two Sat In this problem we must solve the satisfiability of logical formulas which consist of two propositions, without denying or denied joined by OR. There are also several of these formulas, consider the following example: p1∨p3 p2∨¬p1 p2∨¬p3 ¬p1∨¬p2 Note that if p1 is false, and p2, p3 are true, you can meet all the above. I mean, what you should do is to find a truth value for all propositions such that all formulas appraise real. It is not always possible to find a truth value to propositions that achieves satisfying all formulas, consider the following example: p1∨¬p2 p1∨p2 ¬p1∨¬p2 ¬p1∨p2 Any possible combination of truth values ​​for the above propositions can not meet all the rules. The goal here is to make a program that given a set of propositions and rules to determine whether or not it is possible to meet all the rules, and if possible, to say truth values ​​satisfy all the rules. Input: The input consists of several test cases. The first line of each test case contains two integers N and M represent the number of rules and propositions respectively. Then follow N lines with two integers representing a rule, if the integer is positive represetenta the id of the proposition and if negative represents the negated proposition. In the example shown as the first two test cases the examples described above. 1 ≤ N ≤ 10000 1 ≤ M ≤ 5000 output: For each test case print "Yes" or "No" without quotes. If the answer is "Yes" next to this should put an integer indicating the number of true propositions V, and on the next line V integer indicating the number of the true proposition. example: Input: 4 3 +1 +3 +2 -1 +2 -3 -1 -2 4 2 +1 -2 +1 +2 -1 -2 -1 +2 1 3 +1 -3 Output: Yes 2 2 3 No Yes 3 1 2 3 This is the code I made in C++ but I need a new logical solution.. Thanks for your help. #include // Entradas y salidas cout y cin #include // representacion nodos y el vector listas adyacencia #include // insertar y borrar elementos en un punto especifico la lista #include // Implementa Sort, no tener implementar nuestro propio sort using namespace std; // utilizar todo lo esta dentro del estandar C++ y no tener usar std::, aparte saber diferenciar y saber a me estoy refiriendo struct Nodo{ // Reordena los nodos por el tiempo finalizacion y me muestra cual es el nodo originalmente estaba en la posicion int id; int d; // Tiempo Inicializacion int f; // Tiempo finalizacion char color; // Color Nodo *pi; // Pi(papa) }; Void printNodo() { // precisar entrega bien la respuesta Cout<<"id"<v; // Vector nodos vector> al; // Vector lista adyacencia (Vector donde cada nodo se tiene una lista) }; Grafo(){} // Constructor /* int getIndice(int id){ for(int=0;i()); } } void addArista(int u,int v){ // Adiciona una arista a la lista adyacencia } Void printAl() { // poder verificar el grafo quedo bien construido For (int i=0; ib.f; } Void scc(grafo &g) { // Me dice componente es fuertemente conectado Grafo gt = g.transpuesta(); Gt.dfs(); Vectornodos=g.v; Sort(nodos.begin(),nodos Int main() { Int n,e,u,v; Clin >> n >> e; Grafo g(n); For (int i=0; i>u>>v; G.addArista(u,v); } G.printAl  asked 07 May '14, 22:24 1●1●1●1 accept rate: 0%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×1,886
×916
×243
×2
×1

question asked: 07 May '14, 22:24

question was seen: 1,731 times

last updated: 07 May '14, 22:26