开始学习2-Sat，前面看了对称性解决2-sat的ppt，很有帮助。
题意:n对夫妻，夫妻需要出席一人，给出不相容的关系，求每对是否能完成出席方案。
思路：通过关系建图，Tarjan缩点，然后进行判断：条件：若有一对夫妻在同一个连通分量中，即不可组成方案。
代码：
#include <iostream>
#include <stdio.h>
#include <string.h>
using namespace std;
#define E 1000500
#define V 2005
int top,cnt,index,n,m,ecnt;
bool instack[V];
int stack[V],id[V],dfn[V],low[V],in[V];
int head[V];
struct edge{
int s,t,next;
}e[E];
void addedge(int u,int v){
e[ecnt].s=u;
e[ecnt].t=v;
e[ecnt].next=head[u];
head[u]=ecnt++;
}
void tarjan(int u){
int v;
int tmp;
dfn[u]=low[u]=++index;
instack[u]=true;
stack[++top]=u;
for(int k=head[u];k!=-1;k=e[k].next){
v=e[k].t;
if(!dfn[v]){
tarjan(v);
if(low[v]<low[u])
low[u]=low[v];
}
else if(instack[v] && dfn[v]<low[u]){
low[u]=dfn[v];
}
}
if(dfn[u]==low[u]){
cnt++;
do{
tmp=stack[top--];
instack[tmp]=false;
id[tmp]=cnt;
}
while(tmp!=u);
}
}
void build(){
ecnt=0;
memset(head,-1,sizeof(head));
int a1,a2,c1,c2;
while(m--){
scanf("%d%d%d%d",&a1,&a2,&c1,&c2);
if(c1 && c2){
addedge(a1+n,a2);
addedge(a2+n,a1);
}
if(!c1 && c2){
addedge(a1,a2);
addedge(a2+n,a1+n);
}
if(c1 && !c2){
addedge(a1+n,a2+n);
addedge(a2,a1);
}
if(!c1 && !c2){
addedge(a1,a2+n);
addedge(a2,a1+n);
}
}
}
void solve(){
top=cnt=index=0;
memset(dfn,0,sizeof(dfn));
for(int i=0;i<2*n;i++)
if(!dfn[i])
tarjan(i);
}
void judge(){
bool flag=0;
for(int i=0;i<n;i++){
if(id[i]==id[i+n]){
flag=1;
break;
}
}
if(flag) printf("NO
");
else printf("YES
");
}
int main(){
while(scanf("%d%d",&n,&m)!=EOF){
build();
solve();
judge();
}
return 0;
}