【题意】：有一对新人结婚，邀请n对夫妇去参加婚礼。有一张很长的桌子，人只能坐在桌子的两边，还要满足下面的要求：1.每对夫妇不能坐在同一侧 2.n对夫妇之中可能有通奸关系（包括男男，男女，女女），有通奸关系的不能同时坐在新娘的对面，可以分开坐，可以同时坐在新娘这一侧。如果存在一种可行的方案，输出与新娘同侧的人。
【题解】：比较明显的2-sat，我们可以把问题转化为求坐在新娘对面的人的可行方案。
对于m对有通奸关系的x 和 y，连边x->y', y->x'.
最后新娘向新郎连一条边，表示新郎一定要坐在新娘的对面，然后就是解2-sat的基本步骤了，输出方案时利用染色把与新娘同色的人输出。
【代码】：
1 #include "iostream"
2 #include "cstring"
3 #include "cstdio"
4 #include "vector"
5 using namespace std;
6 #define maxn 5010
7 vector<int> vec[maxn], rvec[maxn], dag[maxn];
8 int belong[maxn], scc, top, s[maxn], color[maxn];
9 int n, m;
10 bool visit[maxn];
11 void init() {
12 for(int i = 0; i < maxn; i++) vec[i].clear(), rvec[i].clear(), dag[i].clear();
13 }
14 int cal(int a, char ch) {
15 int res = a * 2;
16 if(ch == 'h') return res;
17 else return res + 1;
18 }
19 void dfs1(int u) {
20 visit[u] = true;
21 int size = vec[u].size();
22 for(int i = 0; i < size; i++) {
23 int v = vec[u][i];
24 if(!visit[v]) dfs1(v);
25 }
26 s[++top] = u;
27 }
28 void dfs2(int u) {
29 visit[u] = true;
30 int size = rvec[u].size();
31 for(int i = 0; i < size; i++) {
32 int v = rvec[u][i];
33 if(!visit[v]) dfs2(v);
34 }
35 belong[u] = scc;
36 }
37 void kosaraju() {
38 scc = top = 0;
39 memset(visit, false, sizeof(visit));
40 for(int i = 0; i < 2 * n; i++)
41 if(!visit[i]) dfs1(i);
42 memset(visit, false, sizeof(visit));
43 for(int i = 2 * n; i; i--)
44 if(!visit[s[i]]) scc++, dfs2(s[i]);
45 for(int u = 0; u < 2 * n; u++) {
46 int size = rvec[u].size();
47 for(int i = 0; i < size; i++) {
48 int v = rvec[u][i];
49 if(belong[u] != belong[v]) dag[belong[u]].push_back(belong[v]);
50 }
51 }
52 }
53 bool solvable() {
54 for(int i = 0; i < 2 * n; i += 2)
55 if(belong[i] == belong[i+1]) return false;
56 return true;
57 }
58 void dfs(int u) {
59 color[u] = 2;
60 int size = dag[u].size();
61 for(int i = 0; i < size; i++) {
62 int v = dag[u][i];
63 if(!color[v]) dfs(v);
64 }
65 }
66 void solve() {
67 memset(color, 0, sizeof(color));
68 for(int i = scc; i; i--) {
69 if(!color[i]) {
70 color[i] = 1;
71 for(int j = 0; j < 2 * n; j++) {
72 if(belong[j] == i) {
73 int k = belong[j^1];
74 if(!color[k]) dfs(k);
75 }
76 }
77 }
78 }
79 for(int i = 2; i < 2 * n; i++)
80 if(color[belong[i]] == color[belong[1]])
81 printf("%d%c ", i / 2, i & 1 ? 'w' : 'h');
82 printf("\n");
83 }
84 void debug() {
85 for(int i = 0; i < 2 * n; i++) {
86 int size = vec[i].size();
87 for(int j = 0; j < size; j++) {
88 cout << i << "->" << vec[i][j] << endl;
89 }
90 }
91 cout << endl;
92 for(int i = 1; i <= scc; i++) {
93 int size = dag[i].size();
94 for(int j = 0; j < size; j++) {
95 cout << i << "->" << dag[i][j] << endl;
96 }
97 }
98 }
99 int main() {
100 char ch1, ch2;
101 int a, b;
102 while(~scanf("%d%d", &n, &m)) {
103 getchar();
104 if(!n && !m) break;
105 init();
106 for(int i = 0; i < m; i++) {
107 scanf("%d%c%d%c", &a, &ch1, &b, &ch2);
108 getchar();
109 int u = cal(a, ch1), v = cal(b, ch2);
110 vec[u].push_back(v^1), vec[v].push_back(u^1);
111 rvec[v^1].push_back(u), rvec[u^1].push_back(v);
112 }
113 vec[1].push_back(0), rvec[0].push_back(1);
114 kosaraju();
115 if(solvable()) solve();
116 else printf("bad luck\n");
117 }
118 return 0;
119 }