题目链接：https://vjudge.net/contest/166461#problem/C

题意：

n对夫妻，有m对人吵过架，不能排在同一边，求新娘的一边的人；

 

分析：

每对夫妻，看成两个点，女的 2i，男的2i+1，吵架了的关系，就是必然关系，必须满足，不能在同一边；再用2-SAT

#include 
      
       using namespace std;const int maxn = 5000+5;struct TwoSAT {    int n;    vector
       
         G[maxn*2];    bool mark[maxn*2];    int S[maxn*2],cnt;    bool dfs(int u) {        if(mark[u^1])   return false;        if(mark[u]) return true;        mark[u]=1;        S[cnt++]=u;        for(int i=0; i
        
         n = n;        for(int i=0; i
         
          0)                        mark[S[--cnt]] = false;                    if(!dfs(i+1)) return false;                }            }        }        return true;    }} sol;int main() {    int n,m;    while(scanf("%d%d",&n,&m),n) {        sol.init(n);        char p[2][3];        int a,b;        while(m--) {            scanf("%d%s%d%s",&a,p[0],&b,p[1]);            int u=0,v=0;            if(p[0][0]=='h')    u=1;            if(p[1][0]=='h')    v=1;            sol.add_clause(a,u,b,v);        }        if(!sol.solve())            printf("bad luck\n");        else {            for(int i=1; i