2-sat。不错的一道题，学到了不少。
需要注意这么几点：
1、题目中描述的是有n对夫妇，其中（n-1）对是来为余下的一对办婚礼的，所以新娘只有一位。
2、2-sat问题是根据必然性建边，比如说A与B二选一，那么当不选A时，必然选B。在本题中，我们所能确定的必然性只有一种：当一对通奸者中的一个人出现在新娘的对面时，另一个必须在新娘的同侧。一开始，我每次建的是两条边，即由新娘指向对面的一人，再从这个人，指向与新娘同侧的另一人（语言描述较困难，但我尽量简明的表达出来）。这是一种假设，因为新娘既可能在左边，又可能在右边。但是这不是必然性：“新娘指向对面的一个人”，这条边不存在必然关系。
解决办法：我们假定新娘就在某一侧。那么是否会影响最终结果呢？不会，因为不管在那一侧，只要有正确方案，转换一下方向，总归是成立的。
3、如何确定新娘就在某一侧？
建边的过程，我们假定了新娘的位置，但是并没有确定的在程序中表现出，新娘就在这一侧。
方法：（1）mark[0]=1;明确的表示出新娘已被标记，但需要注意的是，每次dfs标记的是一条链，或者说是以你选择的点为根的一棵树，所以，只是这样做是不够的，需要单独对mark[0]做一次dfs。
（2）如代码中写的，dfs过程中，若是在 dfs(0) 时失败了，那么就return false;不给 dfs(1) 机会。
注意:准确的说，确定了新娘的位置，即确定了“0w”和“0h”的位置，那么所有包含“0w”或“0h”的关系，所建的边都只能有一条。不过删掉约束条件一样能ac，仔细想来，是solve()中if（i==0）return false;的功劳，因为我只允许dfs(0)成功，所以即使建了另一条边，也不会有机会搜的。
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<vector>
#include<algorithm>
using namespace std; const int MAXN=; int n;
bool mark[MAXN<<];
int S[MAXN<<],c;
vector<int >G[MAXN<<]; void init(int n)
{
for(int i=;i<(n<<);i++)
G[i].clear();
memset(mark,,sizeof(mark));
} void add(int x,int xval,int y,int yval)
{
x=(x<<)+xval;
y=(y<<)+yval;
G[x].push_back(y);
} bool dfs(int x)
{
if(mark[x^]){
return false;
}
if(mark[x]){
return true;
}
S[c++]=x;
mark[x]=true;
for(int i=;i<G[x].size();i++)
{
if(!dfs(G[x][i])){
return false;
}
}
return true;
} bool solve()
{
for(int i=;i<(n<<);i+=)
{
if(!mark[i]&&!mark[i+]){
c=;
if(!dfs(i)){
if(i==) //如果新娘在 0 这一侧这一前提不成立，则 no solusion
return false;
while(c>)
mark[S[--c]]=false;
if(!dfs(i+))
return false;
}
}
}
return true;
} int main()
{
int m,a,b;
char x,y;
while(~scanf("%d%d",&n,&m))
{
if(!n&&!m)
return ; init(n);
for(int i=;i<m;i++) //固定新娘在 0 这一侧
{
scanf("%d%c %d%c",&a,&x,&b,&y);
if(x=='h'&&y=='h'){
add(a,,b,);
add(b,,a,);
}else if(x=='w'&&y=='w'){
add(a,,b,);
add(b,,a,);
}else if(x=='h'&&y=='w'){
add(a,,b,);
add(b,,a,);
}else if(x=='w'&&y=='h'){
add(a,,b,);
add(b,,a,);
}
} if(solve()){
for(int i=;i<n;i++)
{
if(mark[i<<])
printf("%dw",i);
else
printf("%dh",i);
if(i!=n-)
printf(" ");
}
printf("\n");
}else
printf("bad luck\n");
}
return ;
}
/*
附上一组数据，让我发现了第三个问题
10 10
6h 2w
1h 9w
1w 3w
9w 0h
1h 9h
4h 1w
7h 2w
1h 0h
0h 9w
0h 3h
*/