Cod sursa(job #631891)

Utilizator floringh06Florin Ghesu floringh06 Data 9 noiembrie 2011 21:40:19
Problema 2SAT Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 2.7 kb
#include <map>
#include <list>
#include <set>
#include <stack>
#include <queue>
#include <algorithm>
#include <sstream>
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <climits>
#include <cfloat>
#include <numeric>

using namespace std;

const int    oo  = 0x3f3f3f3f;
const double eps = 1e-9;

typedef long long ll;
typedef vector<int> vi;
typedef vector<string> vs;
typedef pair<int, int> pii;

#define sz(c) int ((c).size())
#define all(c) (c).begin(), (c).end()
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define FORD(i, a, b) for (int i = (b) - 1; i >= (a); --i)
#define FORIT(i, c) for (__typeof__((c).begin()) i = (c).begin(); i != (c).end(); ++i)
#define mp make_pair
#define pb push_back
#define MAX_N 200005

int N, M, C;
int comp[MAX_N];
int associate[MAX_N];
bool used[MAX_N];

int value[MAX_N];

vi adj[MAX_N][2], sorted;

vi ncomps[MAX_N];

inline int GetVariable (int v) {
    return (v > 0) ? v - 1 : (-v - 1 + N);   
}

inline int Not (int v) {
    return (v < N) ? v + N : v - N;
}

void DFS (int n, int dir, int c) {
     if (comp[n] != -1) return;
     comp[n] = c;
     FOR (i, 0, sz(adj[n][dir])) DFS (adj[n][dir][i], dir, c);
     if (dir == 0)  sorted.pb(n);
}

void scc () {
     sorted.clear();
     memset (comp, -1, sizeof (comp));
     FOR (i, 0, N) if (comp[i] == -1) DFS (i, 0, 0);
     reverse (all(sorted));
     C = 0;
     memset (comp, -1, sizeof (comp));
     FOR (i, 0, sz(sorted)) 
         if (comp[sorted[i]] == -1) DFS (sorted[i], 1, C++);
}

int main () {
    freopen ("2sat.in", "r", stdin);
    freopen ("2sat.out", "w", stdout);
    
    scanf ("%d %d", &N, &M);
    FOR (i, 0, M) {
        int x, y;
        scanf ("%d %d", &x, &y);
        
        x = GetVariable(x);
        y = GetVariable(y);        
        adj[x][1].pb(Not(y));
        adj[y][1].pb(Not(x));
        
        adj[Not(y)][0].pb(x);
        adj[Not(x)][0].pb(y);
    }
    
    scc();
    
    FOR (i, 0, N)
        if (comp[i] == comp[i + N]) {
           printf ("-1\n");
           return 0;
        }
        
    FOR (i, 0, 2 * N) ncomps[comp[i]].pb(i);
    FOR (i, 0, 2 * N) associate[comp[i]] = comp[Not(i)];
    
    memset (used, false, sizeof (used));
    FOR (i, 0, C) {
        if (used[i]) continue;
        
        FOR (j, 0, sz(ncomps[i])) {
            value[ncomps[i][j]] = 0;
            value[Not(ncomps[i][j])] = 1;
        }
        
        used[i] = true;
        used[associate[i]] = true;
    }
    
    FOR (i, 0, N) if (i != N - 1) printf ("%d ", value[i]); 
                             else printf ("%d\n", value[i]);

    return 0;
}