算法1

(2-sat)

和新娘坐同一端只能是男方或女方，0表示选男和新娘坐一侧1表示选女和新娘坐一侧，符合2-sat条件
有m对狗男女（狗男男（狗女女不能同时坐在新娘的对面，对于每一对狗男女若选择了其中一个人的配偶和新娘坐一侧则可以推出必须选另一个人和新娘坐一侧；

C++ 代码

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<ctime>
#include<cmath>
#include<string>
#include<cstring>
#include<bitset> 
#include<vector>
#include<queue>
#include<stack>
#include<set>
#include<map>
#include<iomanip>
#include<algorithm>
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl "\n"
#define int long long
#define PI  acos(-1)
//CLOCKS_PER_SEC clock()函数每秒执行次数
using namespace std;

const int INF = 0x3f3f3f3f;
const int N = 3e5+5,M = N * 2;
int mod = 1e9 +7;
int n,m,k,S,T;
int e[M],ne[M],h[N],idx;
void add(int a,int b){
    e[idx] = b,ne[idx] = h[a],h[a] = idx++;
}
int dfn[N],low[N],stk[N],id[N],scc_cnt,ts,top;
bool instk[N];
void tarjan(int u){
    dfn[u] = low[u] = ++ts;
    stk[++top] = u,instk[u] = true;
    for(int i = h[u] ; ~i ; i = ne[i]){
        int v = e[i];
        if(!dfn[v]){
            tarjan(v);
            low[u] = min(low[u],low[v]);
        }
        else if(instk[v]) low[u] = min(low[u],dfn[v]);
    }
    if(dfn[u] == low[u]){
        int y;
        scc_cnt++;
        do{
            y = stk[top--];
            instk[y] = false;
            id[y] = scc_cnt;
        }while(y != u);
    }
}
bool check(){
    for(int i = 0 ; i < n ; ++i){
        if(id[i] == id[i + n]) return false;
    }
    return true;
}
void solve(){
    while(cin >> n >> m,n || m){
        memset(h,-1,sizeof(h)),idx = 0;
        //0~n-1为选男，n~2*n-1为选女
        //第0个位置选新娘
        //选男推出选女制约该位置只能选女
        add(0,n);
        while(m--){
            int a,c,pa,pc;
            char b,d;
            cin >> a >> b >> c >> d;
            if(b == 'h') pa = a + n;
            else pa = a,a += n;
            if(d == 'h') pc = c + n;
            else pc = c,c += n;
            //选择a的配偶 --> 选择c 
            add(pa,c);
            //选择c的配偶 --> 选择a 
            add(pc,a);
        }
        memset(dfn,0,sizeof(dfn));
        scc_cnt = top = ts = 0;
        for(int i = 0 ; i < 2 * n ; ++i){
            if(!dfn[i]) tarjan(i);
        }
        if(!check()) cout << "bad luck" << endl;
        else{
            for(int i = 1 ; i < n ; ++i){
                cout << i;
                if(id[i] < id[i + n]) cout << 'h' << ' ';
                else cout << 'w' << ' ';
            }
            cout << endl;
        }
    }
}

signed main(){
    IOS;
    solve();
    return 0;
}
/*
*
*　　┏┓　　　┏┓+ +
*　┏┛┻━━━┛┻┓ + +
*　┃　　　　　　　┃
*　┃　　　━　　　┃ ++ + + +
*  ████━████+
*  ◥██◤　◥██◤ +
*　┃　　　┻　　　┃
*　┃　　　　　　　┃ + +
*　┗━┓　　　┏━┛
*　　　┃　　　┃ + + + +Code is far away from 　
*　　　┃　　　┃ + bug with the animal protecting
*　　　┃　 　 ┗━━━┓ 神兽保佑,代码无bug　
*　　　┃ 　　　　　　 ┣┓
*　　  ┃ 　　　　　 　┏┛
*　    ┗┓┓┏━┳┓┏┛ + + + +
*　　　　┃┫┫　┃┫┫
*　　　　┗┻┛　┗┻┛+ + + +
*/