Cod sursa(job #382683)

Utilizator CezarMocanCezar Mocan CezarMocan Data 14 ianuarie 2010 13:06:53
Problema 2SAT Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 1.4 kb
#include <cstdio>
#include <algorithm>

#define MAXN 100100
#define MAXM 100100

using namespace std;

int N, M;
pair <int, int> EXPR[MAXM];
int STACK[MAXN], SOL[MAXN];
bool found_sol;

bool eval_term(pair <int, int> T) {
    int x, y;
    
    x = STACK[abs(T.first)];
    y = STACK[abs(T.second)];
    
    if (T.first < 0)
        x ^= 1;
    if (T.second < 0)
        y ^= 1;
        
    return (x | y);
}

bool check_solution() {
    int i;
    
    for (i = 1; i <= M; i++) 
        if (!eval_term(EXPR[i]))
            return false;
            
    return true;
}

void generate_solution(int K) {
    int i, bit;
	if (found_sol)
		return;
    if (K == N) {
        if (check_solution() == true) {
            for (i = 1; i <= N; i++)
                SOL[i] = STACK[i]; 
            found_sol = true;
        }    
    }
    else {
        for (bit = 0; bit < 2; bit++) {
            STACK[K + 1] = bit;
            generate_solution(K + 1);
        }
    }    
}


int main(){
    
    int i, a, b;
    
    freopen("2sat.in", "r", stdin);
    freopen("2sat.out", "w", stdout);
    
    scanf("%d%d", &N, &M);
    for (i = 1; i <= M; i++) {
        scanf("%d%d", &a, &b);
        EXPR[i] = make_pair(a, b);
    }
    
    found_sol = false;
    generate_solution(0);
    
    if (!found_sol) 
        printf("-1\n");
    else {
        for (i = 1; i <= N; i++)
            printf("%d ", SOL[i]);   
    }

    return 0;
}