From b6890ddadfe760cff46392cc4f826d8b84d128cd Mon Sep 17 00:00:00 2001 From: Yidi Date: Sat, 9 Mar 2024 18:48:22 +0100 Subject: shorten 2sat --- graph/2sat.cpp | 16 +++++----------- 1 file changed, 5 insertions(+), 11 deletions(-) diff --git a/graph/2sat.cpp b/graph/2sat.cpp index 8fb3d39..75e54e6 100644 --- a/graph/2sat.cpp +++ b/graph/2sat.cpp @@ -2,7 +2,7 @@ struct sat2 { int n; // + scc variablen vector sol; - sat2(int vars) : n(vars*2), adj(vars*2) {}; + sat2(int vars) : n(vars*2), adj(n) {} static int var(int i) {return i << 1;} // use this! @@ -18,20 +18,14 @@ struct sat2 { void addAnd(int a, int b) {addTrue(a); addTrue(b);} void addNand(int a, int b) {addOr(1^a, 1^b);} - bool solvable() { + bool solve() { scc(); //scc code von oben + sol.assign(n, -1); for (int i = 0; i < n; i += 2) { if (idx[i] == idx[i + 1]) return false; + sol[i] = idx[i] < idx[i + 1]; + sol[i + 1] = !sol[i]; } return true; } - - void assign() { - sol.assign(n, -1); - for (int i = 0; i < sccCounter; i++) { - if (sol[sccs[i][0]] == -1) { - for (int v : sccs[i]) { - sol[v] = 1; - sol[1^v] = 0; - }}}} }; -- cgit v1.2.3