第一次接触2-SAT——SAT,即适定性（Satisfiability）的缩写。像名称所说，即满足需求的可能性问题，而k-SAT即每个人有k种需求，已经证明k>2时是一个NP完全问题。所以现在常见的考法便是2-SAT。

这一道题目算是一道裸的2-SAT问题。每一个人有两种需求，那么我们就将每一种食物拆成两个点，一个代表m,一个代表h，可以注意到满足所有人的需求即如果满足不了其中一个，必须满足另一个，所以我们建图的方法为从无法满足要求的点连向必须满足的点，代表若一个点不符合要求，必然走向后续的决策。那么问题的答案相比到这里已经比较明了了。我们就应当在这张图上求出强连通分量，看是否有一个点的两个拆点都存在于同一个强连通分量上。若是如此，就说明无法满足要求。

#include 
     
      using namespace std;#define maxn 100000int T, cnt, cnp = 1, n, m, low[maxn], dfn[maxn], num[maxn], timer, head[maxn];bool flag, mark[maxn], vis[maxn];stack 
      
        st;struct edge{    int to, last;}E[maxn];int read(){    int x = 0;    char c;    c = getchar();    while(c < '0' || c > '9') c = getchar();    while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();    return x;}void add(int u, int v){    E[cnp].to = v, E[cnp].last = head[u], head[u] = cnp ++;}void tarjan(int u){    dfn[u] = low[u] = ++ timer;    vis[u] = true, mark[u] = true;    st.push(u);    for(int i = head[u]; i; i = E[i].last)    {        int v = E[i].to;        if(vis[v])        　　{ if(mark[v] && low[u] > dfn[v]) low[u] = dfn[v]; }        else         {            tarjan(v);            low[u] = min(low[u], low[v]);        }    }    if(dfn[u] == low[u])    {        ++ cnt;        int j;        do        {            j = st.top();            st.pop();            mark[j] = false;            num[j] = cnt;        }while(!st.empty() && j != u);    }}void init(){    memset(vis, 0, sizeof(vis));    memset(head, 0, sizeof(head));    cnp = 1, timer = 0;    flag = false;}int main(){    T = read();    while(T --)    {        n = read(), m = read();        init();        for(int i = 1; i <= m; i ++)        {            char c1, c2;            int d1, d2;            cin >> c1 >> d1 >> c2 >> d2;            int a = 0, b = 0;            a += (c1 == 'h'), b += (c2 == 'h');            add(((2 * d2) + b) ^ 1, (2 * d1) + a);            add(((2 * d1) + a) ^ 1, 2 * d2 + b);        }        for(int i = 2; i <= 2 * n + 1; i ++)            if(!vis[i]) tarjan(i);        for(int i = 2; i <= 2 * n; i += 2)            if(num[i] == num[i ^ 1])             {                printf("BAD\n");                flag = true; break;            }        if(!flag) printf("GOOD\n");    }    return 0;}