C++ 代码
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using namespace std;
struct two_sat {
int n;
vector<vector<int>> to;
vector<bool> ans;
two_sat(int n): n(n), to(2*n), ans(n) {}
void add_clause(int i, bool a, int j, bool b) {
to[2*i+!a].push_back(2*j+b);
to[2*j+!b].push_back(2*i+a);
}
bool satisfiable() {
int n2 = 2*n;
vector<int> id(n2, -1), ord(n2, -1), low(n2, -1);
stack<int> stk;
int now_ord = 0, group_num = 0;
auto dfs = [&](auto& f, int v) -> void {
stk.push(v);
ord[v] = low[v] = now_ord++;
for (int u : to[v]) {
if (ord[u] == -1) {
f(f, u);
low[v] = min(low[v], low[u]);
}
else if (id[u] == -1) {
low[v] = min(low[v], ord[u]);
}
}
if (ord[v] == low[v]) {
int u;
do {
u = stk.top(); stk.pop();
id[u] = group_num;
} while (u != v);
++group_num;
}
};
rep(i, n2) if (ord[i] == -1) dfs(dfs, i);
rep(i, n) {
if (id[2*i] == id[2*i+1]) return false;
ans[i] = id[2*i] > id[2*i+1];
}
return true;
}
vector<bool> answer() { return ans; }
};
int main() {
cin.tie(nullptr) -> sync_with_stdio(false);
int n, m;
cin >> n >> m;
two_sat ts(n);
rep(mi, m) {
int i, a, j, b;
cin >> i >> a >> j >> b;
--i; --j;
ts.add_clause(i, a, j, b);
}
if (!ts.satisfiable()) cout << "IMPOSSIBLE\n";
else {
cout << "POSSIBLE\n";
for (int x : ts.answer()) cout << x << ' ';
}
return 0;
}