思路：将每对夫妻看成是对立状态，每个不正常关系都是一个矛盾，按2-SAT的方式建边。最后建一条新娘到新郎的边。具体看注释
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
#define Maxn 62
#define Maxm Maxn*Maxn
using namespace std;
int vi[Maxn],head[Maxn],dfn[Maxn],low[Maxn],e,n,lab,top,num,id[Maxn],Stack[Maxn],in[Maxn],Hash[Maxn],col[Maxn];
struct Edge{
int u,v,next;
}edge[Maxm];
void init()//初始化
{
memset(vi,,sizeof(vi));
memset(head,-,sizeof(head));
memset(dfn,,sizeof(dfn));
memset(low,,sizeof(low));
memset(id,,sizeof(id));
memset(in,,sizeof(in));
memset(col,,sizeof(col));
e=lab=top=num=;
}
void add(int u,int v)//加边
{
edge[e].u=u,edge[e].v=v,edge[e].next=head[u],head[u]=e++;
}
void Tarjan(int u)//找出强连通分支
{
int i,j,v;
dfn[u]=low[u]=++lab;
Stack[top++]=u;
vi[u]=;
for(i=head[u];i!=-;i=edge[i].next)
{
v=edge[i].v;
if(!dfn[v])
{
Tarjan(v);
low[u]=min(low[u],low[v]);
}
if(vi[v])
low[u]=min(low[u],dfn[v]); }
if(low[u]==dfn[u])
{
++num;
do{
i=Stack[--top];
vi[i]=;
id[i]=num;
}while(i!=u);
}
}
void buildGraphic()//缩点后重新建树，以便进行拓扑排序
{
int ed=e,u,v;
memset(head,-,sizeof(head));
e=;
int i;
for(i=;i<ed;i++)
{
u=edge[i].u;
v=edge[i].v;
if(id[u]!=id[v])
{
add(id[v],id[u]);//由于2-SAT问题中是找出度为0的点，这里我们建个反图，方便进行拓扑排序，变成找入度为0的点
in[id[u]]++;
}
}
}
void Topsort()
{
int i,j,u,v,temp;
queue<int> q;
int fron,rear;
fron=rear=;
for(i=;i<=num;i++)
if(in[i]==)
q.push(i);
while(!q.empty())
{
temp=q.front();
q.pop();
if(!col[temp]) col[temp]=,col[Hash[temp]]=;//如果该连通分支未着色，那么给他着1，它的对立点就必须着不同的色
for(i=head[temp];i!=-;i=edge[i].next)
{
v=edge[i].v;
in[v]--;
if(in[v]==)
q.push(v);
}
}
}
int solve()
{
int i,j;
for(i=;i<=*n;i++)
if(!dfn[i])
Tarjan(i);
for(i=;i<=n;i++)
if(id[i]==id[i+n])
return ;//有矛盾则结束
else
Hash[id[i]]=id[i+n],Hash[id[i+n]]=id[i];//标记每个连通分支间的对立关系,即不能再同一侧 buildGraphic();
Topsort();
for(i=;i<=n;i++)
if(col[id[i]]==col[id[n+]]) printf("%dh ",i-);//输出和新娘同侧的人
else printf("%dw ",i-);
printf("\n");
return ;
}
int op(int x)
{
if(x<=n) return x+n;
return x-n;
}
int main()
{
int m,i,j,a,b;
char c1,c2;
while(scanf("%d%d",&n,&m),n|m)
{
init();
for(i=;i<m;i++)
{
scanf("%d%c%d%c",&a,&c1,&b,&c2);//husband点为1~N,wife点为N+1~2*N
a++,b++;
if(c1=='w')
a+=n;
if(c2=='w')
b+=n;
add(a,op(b));
add(b,op(a));
}//我们的目标是选择和新郎同一侧的，新郎固然在自己一侧。
add(n+,);//建一条由新娘到新郎的边，若选择了新娘，新郎也会被选，新郎和新娘成了同侧，便矛盾。即新娘不能和新郎同一侧
if(!solve())
printf("bad luck\n");
}
return ;
}