题意：
一开始题读错了，囧，看了题解才发现，汗！
有一对夫妻要结婚，他们坐在一条长凳上，这条长方形长凳有左右两端（自行脑补），来了若干对夫妻参加他们的婚礼。
规定一对夫妻中的两个人不能坐在同一端。
新娘因为头饰太复杂所以看不到跟她坐在同一侧的人。
同时这些夫妻中有某些人存在不纯洁关系，新娘不希望同时看见有不纯结关系的两个人，也就是说，存在不纯洁关系的两个人不能同时在新娘的对侧，但是可以同时坐在新娘的同侧。
判断是否存在一个安排方案使得满足上述条件，如果存在，输出坐在新娘同侧的人，否则说明不可能。
思路：
2-SAT。
首先假设新娘在左侧（假设右侧也可以，修改相关条件即可）
把每个人看成一个点，那么假设坐在左侧为真，右侧为假。
首先，对于每一对夫妻i和j，不能坐在同一侧，那么Xi和Xj不能同时为真，也不能同时为假，根据这两个限制条件就加两条边。
其次，对于每一对有不纯洁关系的人，只要他们不同时坐在新娘的对侧就满足条件，只要Xi和Xj中至少一个为真即可，根据这个条件加边。
要注意的一点是，因为新娘必须坐在新娘的同侧，所以一开始要把新娘赋值为真，因为新娘在左侧。
输出的时候不输出新娘。
代码：
1 #include2 #include 3 #include 4 #include 5 #include 6 using namespace std; 7 8 const int maxn = 200005; 9 10 vector ans; 11 12 struct twosat 13 { 14 int n; 15 vector g[maxn*2]; 16 bool mark[maxn*2]; 17 int s[maxn*2],c; 18 19 bool dfs(int x) 20 { 21 //printf("orz"); 22 if (mark[x^1]) return false; 23 if (mark[x]) return true; 24 25 mark[x] = true; 26 27 s[c++] = x; 28 29 for (int i = 0;i < g[x].size();i++) 30 { 31 if (!dfs(g[x][i])) return false; 32 } 33 34 return true; 35 } 36 37 void init(int n) 38 { 39 this -> n = n; 40 for (int i = 0;i <= 2 * n;i++) g[i].clear(); 41 memset(mark,0,sizeof(mark)); 42 } 43 44 void add_clause(int x,int xval,int y,int yval) 45 { 46 x = x * 2 + xval; 47 y = y * 2 + yval; 48 49 g[x^1].push_back(y); 50 g[y^1].push_back(x); 51 } 52 53 bool solve() 54 { 55 for (int i = 0;i < 2 * n;i += 2) 56 { 57 if (!mark[i] && !mark[i+1]) 58 { 59 c = 0; 60 61 if (!dfs(i)) 62 { 63 while (c > 0) mark[s[--c]] = false; 64 if (!dfs(i+1)) return false; 65 } 66 } 67 } 68 69 return true; 70 } 71 } twosat; 72 73 int main() 74 { 75 int n,m; 76 77 while (scanf("%d%d",&n,&m) != EOF) 78 { 79 if (n == 0 && m == 0) break; 80 ans.clear(); 81 82 twosat.init(n * 2); 83 84 for (int i = 0;i < n;i++) 85 { 86 twosat.add_clause(i,1,i+n,1); 87 twosat.add_clause(i,0,i+n,0); 88 } 89 90 for (int i = 0;i < m;i++) 91 { 92 int a,b; 93 char p[10],q[10]; 94 95 scanf("%d%s%d%s",&a,p,&b,q); 96 97 if (p[0] == 'w') a += n; 98 if (q[0] == 'w') b += n; 99 100 twosat.add_clause(a,1,b,1);101 //twosat.add_clause(a,0,b,0);102 }103 104 twosat.mark[2 * n + 1] = 1;105 106 bool f = twosat.solve();107 108 if (f)109 {110 for (int i = 0;i < n * 2;i++)111 {112 if (twosat.mark[2 * i + 1])113 {114 if (i == n) continue;115 ans.push_back(i);116 } 117 }118 119 if (ans[0] >= n)120 {121 printf("%dw",ans[0]-n);122 //printf("orz\n");123 }124 else125 {126 printf("%dh",ans[0]);127 }128 129 for (int i = 1;i < ans.size();i++)130 {131 if (ans[i] >= n)132 {133 printf(" %dw",ans[i]-n);134 }135 else136 {137 printf(" %dh",ans[i]);138 }139 }140 }141 else142 {143 printf("bad luck\n");144 }145 }146 147 return 0;148 }