# Cod sursa(job #631521)

Utilizator Data 8 noiembrie 2011 13:11:15 2SAT 10 cpp done Arhiva educationala 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 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;
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);

}

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[i + N];

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;
}
``````