有n对夫妻被邀请参加一个聚会，因为场地的问题，每对夫妻中只有1人可以列席。在2n 个人中，某些人之间有着很大的矛盾（当然夫妻之间是没有矛盾的），有矛盾的2个人是不会同时出现在聚会上的。有没有可能会有n 个人同时列席？
Input
n： 表示有n对夫妻被邀请 (n<= 1000)
m： 表示有m 对矛盾关系 ( m < (n - 1) * (n -1))

在接下来的m行中，每行会有4个数字，分别是 A1,A2,C1,C2
A1,A2分别表示是夫妻的编号
C1,C2 表示是妻子还是丈夫 ，0表示妻子 ，1是丈夫
夫妻编号从 0 到 n -1
Output
如果存在一种情况 则输出YES
否则输出 NO
Sample Input
2
1
0 1 1 1
Sample Output
YES

很明显的2-SAT，直接先逻辑连边，然后tarjan即可。

注意注释的部分，一个人不去，不能推出另一个人去，所以我们不能加边！！！

AC代码：

#pragma GCC optimize(2)
#include<bits/stdc++.h>
//#define int long long
using namespace std;
const int N=10010,M=1e6+10;
int n,m,vis[N],low[N],dfn[N],cnt,col[N],co,base,flag;
int head[N],nex[M],to[M],tot;
stack<int> st;
inline void add(int a,int b){
	to[++tot]=b; nex[tot]=head[a]; head[a]=tot;
}
inline void init(){
	memset(head,0,sizeof head); tot=flag=co=cnt=0;
	memset(col,0,sizeof col);	memset(dfn,0,sizeof dfn);
	memset(vis,0,sizeof vis);	while(st.size())	st.pop();
}
void tarjan(int x){
	low[x]=dfn[x]=++cnt; vis[x]=1;	st.push(x);
	for(int i=head[x];i;i=nex[i]){
		if(!dfn[to[i]]){
			tarjan(to[i]);	low[x]=min(low[x],low[to[i]]);
		}else if(vis[to[i]]) low[x]=min(low[x],dfn[to[i]]);
	}
	if(low[x]==dfn[x]){
		co++;	int u;
		do{
			u=st.top();	st.pop();	col[u]=co;	vis[u]=0;
		}while(u!=x);
	}
}
signed main(){
	while(~scanf("%d %d",&n,&m)){
		init();	base=n<<1;
		for(int i=1;i<=n;i++)	
			add(i,i+n+base),add(i+n,i+base),add(i+base,i+n),add(i+n+base,i);
		while(m--){
			int a1,a2,c1,c2; scanf("%d %d %d %d",&a1,&a2,&c1,&c2);
			a1++; a2++;
			add(a1+(c1^1)*n,a2+(c2^1)*n+base);
			add(a2+(c2^1)*n,a1+(c1^1)*n+base);
		// add(a1+(c1^1)*n+base,a2+(c2^1)*n);
		// add(a2+(c2^1)*n+base,a1+(c1^1)*n);
		}
		for(int i=1;i<=base<<1;i++)	if(!dfn[i])	tarjan(i);
		for(int i=1;i<=base&&!flag;i++)	if(col[i]==col[i+base])	flag++;
		puts(flag?"NO":"YES");
	}
	return 0;
}