大型补档计划
根据题意，显然只有新郎这边可能存在矛盾，考虑这边怎么放即可，新娘那边的放法与这边正好相反且一一对应。
显然对于两个约束条件是一对矛盾，开始我以为可以用并查集，后来发现输出方案的时候，如果两者都可以的话不会选了只能乱选，有可能会限制死某些变量，需要指数级别 \(dfs\) 搞，然后就放弃了。
设 \([0, n - 1]\) 是这个位置放妻子，\([n, 2 * n - 1]\) 是这个位置放丈夫。
对于这种矛盾 \(a, b\)，构建 2-SAT 模型就是连边 \((a, opp[b]), (b, opp[a])\) （opp表示同样位置的对应元素。）
方案输出按照板子输出即可，注意输出的是新娘一边的，正好我们求的新郎正相反
#include <cstdio>
#include <iostream>
#include <cstring>
using namespace std;
const int N = 65, M = 2005;
int n, m, dfn[N], low[N], dfncnt, s[N], top, c[N], cnt;
bool ins[N];
int opp(int x) { return x <= n - 1 ? x + n : x - n; }
int head[N], numE = 0;
struct E{
int next, v;
} e[M];
void add(int u, int v) {
e[++numE] = (E) { head[u], v };
head[u] = numE;
}
void tarjan(int u) {
dfn[u] = low[u] = ++dfncnt;
ins[u] = true, s[++top] = u;
for (int i = head[u]; i; i = e[i].next) {
int v = e[i].v;
if (!dfn[v]) tarjan(v), low[u] = min(low[u], low[v]);
else if(ins[v]) low[u] = min(low[u], dfn[v]);
}
if (dfn[u] == low[u]) {
int v; ++cnt;
do {
v = s[top--], c[v] = cnt, ins[v] = false;
} while (v != u);
}
}
void clear() {
memset(dfn, 0, sizeof dfn);
memset(head, 0, sizeof head);
memset(c, 0, sizeof c);
memset(ins, false, sizeof ins);
numE = dfncnt = top = cnt = 0;
}
bool check() {
for (int i = 0; i <= n - 1; i++) if (c[i] == c[i + n]) return false;
return true;
}
int main() {
while(scanf("%d%d", &n, &m), n || m) {
clear();
add(0, n);
for (int i = 1, x, y; i <= m; i++) {
char a, b; scanf("%d%c%d%c", &x, &a, &y, &b);
if (a == 'h') x += n;
if (b == 'h') y += n;
add(x, opp(y)), add(y, opp(x));
}
for (int i = 0; i <= 2 * n - 1; i ++) if (!dfn[i]) tarjan(i);
if (!check()) puts("bad luck");
else {
for (int i = 1; i <= n - 1; i++) printf("%d%c ", i, c[i] < c[i + n] ? 'h' : 'w');
puts("");
}
}
}