2-SAT (lib/graph/two_sat.hpp)

View this file on GitHub
Last update: 2025-06-10 13:56:45+09:00
Include: #include "lib/graph/two_sat.hpp"

Depends on

Verified with

test/yosupo/other/two_sat.test.cpp

Code

#pragma once
#include <vector>
#include "graph/scc.hpp"
#include "internal/internal_csr.hpp"

/// @brief 2-SAT
struct two_sat {
    two_sat(int n) : _size(n), G(n * 2) {}

    void add(int i, bool f, int j, bool g) {
        i <<= 1, j <<= 1;
        G.add_edge(i + (f ? 0 : 1), j + (g ? 1 : 0));
        G.add_edge(j + (g ? 0 : 1), i + (f ? 1 : 0));
    }

    std::vector<int> solve() {
        G.build();
        auto res = scc(G);
        return res;
    }

    bool is_satisfy(const std::vector<int> &v) {
        for (int i = 0; i < _size; ++i) {
            if (v[i * 2] == v[i * 2 + 1]) return false;
        }
        return true;
    }

    std::vector<bool> build(const std::vector<int> &v) {
        std::vector<bool> res(_size);
        for (int i = 0; i < _size; ++i) res[i] = v[i * 2] < v[i * 2 + 1];
        return res;
    }

  private:
    int _size;
    internal::graph_csr G;
};

Traceback (most recent call last):
  File "/home/runner/.local/lib/python3.12/site-packages/competitive_verifier/oj/resolver.py", line 291, in resolve
    bundled_code = language.bundle(path, basedir=basedir)
                   ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "/home/runner/.local/lib/python3.12/site-packages/competitive_verifier/oj/verify/languages/cplusplus.py", line 242, in bundle
    bundler.update(path)
  File "/home/runner/.local/lib/python3.12/site-packages/competitive_verifier/oj/verify/languages/cplusplus_bundle.py", line 479, in update
    self._resolve(pathlib.Path(included), included_from=path)
  File "/home/runner/.local/lib/python3.12/site-packages/competitive_verifier/oj/verify/languages/cplusplus_bundle.py", line 286, in _resolve
    raise BundleErrorAt(path, -1, "no such header")
competitive_verifier.oj.verify.languages.cplusplus_bundle.BundleErrorAt: graph/scc.hpp: line -1: no such header