终于搞懂了\(2-sat\)。实际上是个挺简单的东西，像网络流一样关键在于建模。

问题：\(n\)个数\(A\)，可以选择\(0\)和\(1\)，现在给你\(m\)组条件\(A\)，\(B\)，对每个条件要求\(A\)为真或者\(B\)为真。

\(2-sat\)的建图方法：把每一个或条件拆成两个。例如对于条件\(A\) \(or\) \(B\)：

• 如果\(A\)为假，那么\(B\)必须为真。（\(A_false\) \(->\) \(B_true\)）
• 如果\(B\)为假，那么\(A\)必须为真。（\(B_false\) \(->\) \(A_true\)）

即一条边代表一条指向条件，选择一个点就代表着同时要选择它的闭合子图中的其他点。容易知道：如果存在一个圈，其中同时包含\(x_false\)和\(x_true\)，那么取值选择无解。这个过程可以用\(Tarjan\)求\(scc\)来做。

可行解的构造：把原图缩成若干\(scc\)后，对每个条件\(A\)，我们优先选对应点拓扑序比较大的那个值，这样就可以向着最容易出解的方向选择。（选择一个点就代表着同时要选择它的闭合子图中的其他点。）

特定解的构造：暴力。此问题\(np\)完全。

#include 
    
     using namespace std;const int N = 200 + 5;const int M = 2000 + 5;struct Graph {    int cnt, head[N];    struct Edge {        int nxt, to;    }e[M];        void clear () {        cnt = -1;        memset (head, -1, sizeof (head));    }    void add_edge (int u, int v) {        e[++cnt] = (Edge) {head[u], v}; head[u] = cnt;    }    stack 
     
       sta;        int _dfn, _sccid;    int inq[N], dfn[N], low[N], sccid[N];    void Tarjan (int u) {        dfn[u] = low[u] = ++_dfn;        inq[u] = true; sta.push (u);        for (int i = head[u]; ~i; i = e[i].nxt) {            int v = e[i].to;            if (!dfn[v]) {                Tarjan (v);                low[u] = min (low[u], low[v]);            } else if (inq[v]) {                low[u] = min (low[u], dfn[v]);            }        }        if (dfn[u] == low[u]) {            int tmp; ++_sccid;            do {                tmp = sta.top ();                inq[tmp] = false;                sccid[tmp] = _sccid;                sta.pop ();            }while (tmp != u);        }     }        void get_scc (int n) {        _dfn = _sccid = 0;        memset (inq, 0, sizeof (inq));        memset (dfn, 0, sizeof (dfn));        for (int i = 1; i <= n; ++i) {            if (!dfn[i]) Tarjan (i);        }    }    }G;int T, n, m;int node (int x, int t) {    return n * t + x;}int main () {    // freopen ("data.in", "r", stdin);    cin >> T;    while (T--) {        cin >> n >> m; G.clear ();        for (int i = 1; i <= m; ++i) {            static int u, v, t1, t2;            while (!isalpha (t1 = getchar ())); cin >> u;            while (!isalpha (t2 = getchar ())); cin >> v;            t1 = t1 == 'm' ? 0 : 1;            t2 = t2 == 'm' ? 0 : 1;            G.add_edge (node (u, !t1), node (v, t2));            G.add_edge (node (v, !t2), node (u, t1));        }        G.get_scc (n << 1);        bool succ = true;        for (int i = 1; i <= n; ++i) {            if (G.sccid[node (i, 0)] == G.sccid[node (i, 1)]) {                succ = false; break;            }        }        puts (succ ? "GOOD" : "BAD");    }}