diff options
| -rw-r--r-- | content/graph/2sat_amo.cpp | 31 | ||||
| -rw-r--r-- | content/graph/graph.tex | 4 |
2 files changed, 5 insertions, 30 deletions
diff --git a/content/graph/2sat_amo.cpp b/content/graph/2sat_amo.cpp index d50e77d..9686f11 100644 --- a/content/graph/2sat_amo.cpp +++ b/content/graph/2sat_amo.cpp @@ -1,35 +1,6 @@ -constexpr int var(int i) {return i << 1;} // use this! -struct sat2 { - int n; // + scc variablen - vector<int> sol; - 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);} - - 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 atMostOne(const vector<ll>& vars) { int k = n / 2; - n += 2 * sz(vars); + n += 2 * ssize(vars); adj.resize(n); for (int i = 0; i + 1 < sz(vars); i++) { addImpl(vars[i], var(k+i)); diff --git a/content/graph/graph.tex b/content/graph/graph.tex index f6f3d02..b27db0b 100644 --- a/content/graph/graph.tex +++ b/content/graph/graph.tex @@ -92,6 +92,10 @@ \begin{algorithm}{2-SAT} \sourcecode{graph/2sat.cpp} + \optional{ + \subsubsection{At most one \opthint} + \sourcecode{graph/2sat_amo.cpp} + } \end{algorithm} \begin{algorithm}{Artikulationspunkte, Brücken und BCC} |