diff options
Diffstat (limited to 'content/graph/2sat.cpp')
| -rw-r--r-- | content/graph/2sat.cpp | 32 |
1 files changed, 16 insertions, 16 deletions
diff --git a/content/graph/2sat.cpp b/content/graph/2sat.cpp index 3e0811f..d4c8b7b 100644 --- a/content/graph/2sat.cpp +++ b/content/graph/2sat.cpp @@ -1,28 +1,28 @@ -constexpr int var(int i) {return i << 1;} // use this! -struct sat2 { - int n; // + scc variablen +constexpr int var(int i) { return i << 1; } // use this! +struct SAT2 { + int n; + vector<vector<int>> adj; vector<int> sol; - sat2(int vars) : n(vars*2), adj(n) {} + SAT2(int vars) : n(vars*2), adj(n) {} void addImpl(int a, int b) { adj[a].push_back(b); adj[1^b].push_back(1^a); } - void addEquiv(int a, int b) {addImpl(a, b); addImpl(b, a);} - void addOr(int a, int b) {addImpl(1^a, b);} - void addXor(int a, int b) {addOr(a, b); addOr(1^a, 1^b);} - void addTrue(int a) {addImpl(1^a, a);} - void addFalse(int a) {addTrue(1^a);} - void addAnd(int a, int b) {addTrue(a); addTrue(b);} - void addNand(int a, int b) {addOr(1^a, 1^b);} + void addEquiv(int a, int b) { addImpl(a, b); addImpl(b, a); } + void addOr(int a, int b) { addImpl(1^a, b); } + void addXor(int a, int b) { addEquiv(a, 1^b); } + void addTrue(int a) { addImpl(1^a, a); } + void addFalse(int a) { addTrue(1^a); } + void addAnd(int a, int b) { addTrue(a); addTrue(b); } + void addNand(int a, int b) { addOr(1^a, 1^b); } bool solve() { - scc(); //scc code von oben + SCC scc(adj); // SCC @\sourceref{graph/scc.cpp}@ 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]; + for (int i = 0; i < n; i++) { + if (scc.idx[i] == scc.idx[1^i]) return false; + sol[i] = scc.idx[i] < scc.idx[1^i]; } return true; } |