Uva(11294)(Wedding)

链接：https://vjudge.net/problem/UVA-11294
思路：再一次深刻领悟到了2-SAT的一些东西，这个题首先要合点，把夫妇（或者说新郎新娘）变为一个点的两个状态，即一个凳子上要吗只坐新郎要吗只坐新娘，就可以变为2-SAT的模型，然后按照序号依次查看其mark[2*i]的值判断坐的是新郎还是新娘，最后输出即可，特别坑的地方就是要注意起始状态是0号的新娘，而不是说0号新郎新娘都可以，有两种办法，要吗mark[0]标为1，要吗从i=2开始进行2-SAT算法运行。
代码：

#include<cstdio>
#include<vector>
#include<cstring>
#include<algorithm>
#include<deque>
using namespace std;

const int maxn = 50003;
int n,m;

struct twosat{
vector<int> G[maxn];
int n;
bool mark[maxn*2];
int S[maxn*2];
int c;

bool dfs(int x){
    if(mark[x^1])return false;
    if(mark[x])return true;
    mark[x] = true;
    S[c++] = x;
    for(int i=0;i<G[x].size();i++)
        if(!dfs(G[x][i]))return false;
    return true;
}   

void init(int n){
    this->n = n;
    for(int i=0;i<n*2;i++)G[i].clear();
        memset(mark,0,sizeof(mark));
    mark[0]= 1;
}

void add_clause(int x,int xval,int y,int yval){
    x = x*2+xval;
    y = y*2+yval;
    G[x^1].push_back(y);
    G[y^1].push_back(x);
}

bool solve(){
    for(int i=0;i<n*2;i+=2){
        if(!mark[i]&&!mark[i+1]){
            c = 0;
            if(!dfs(i)){
                while(c>0)mark[S[--c]] = false;
                if(!dfs(i+1))return false;
            }
        }
    }
    return true;
}
};

twosat solver;
int main(){
    freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);
    while(scanf("%d%d",&n,&m)!=EOF){
        solver.init(n);
        for(int i=0;i<m;i++){
                int now1,now2;
                char str1,str2;
                scanf("%d%c %d%c",&now1,&str1,&now2,&str2);
                int sex1,sex2;
                if(str1=='h')sex1 = 1;
                else sex1 = 0;
                if(str2=='h')sex2 = 1;
                else sex2 = 0;
                solver.add_clause(now1,sex1,now2,sex2);
            }
            if(!solver.solve())printf("bad luck\n");
            else{
            for(int i=1;i<n;i++){
                if(i!=1)printf(" ");
                printf("%d%c",i,solver.mark[2*i]?'w':'h');
            }
            printf("\n");
        }
    }
    return 0;
}