TwoSat

need getStronglyConnectedComponent.

struct TwoSat { // x : x << 1 | 1, not x : x << 1
  int n;
  std::vector<std::vector<int>> g;
  std::vector<int> scc_id;

  TwoSat(int n) : n(n), g(n << 1) {
    void(0);
  }

  void addClause(int u, bool bu, int v, bool bv) {
    assert(0 <= u && u < n);
    assert(0 <= v && v < n);
    g[u << 1 | !bu].push_back(v << 1 | bv);
    g[v << 1 | !bv].push_back(u << 1 | bu);
  }

  void solve() {
    scc_id = getScc(g);
  }

  [[nodiscard]] bool satisfiable() const {
    for (int i = 0; i < n; ++i) {
      if (scc_id[i << 1] == scc_id[i << 1 | 1]) {
        return false;
      }
    }
    return true;
  }

  [[nodiscard]] std::vector<bool> answer() const {
    std::vector<bool> res(n);
    for (int i = 0; i < n; ++i) {
      assert(scc_id[i << 1] != scc_id[i << 1 | 1]);
      res[i] = (scc_id[i << 1] < scc_id[i << 1 | 1]);
    }
    return res;
  }
};