Problem Description

有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

 

Source

2009 Multi-University Training Contest 16 - Host by NIT

/*2-sat建图有点麻烦，每次要考虑很多，刚学，好多不懂，对于这道题，

有两种矛盾关系一是夫妻之间不能同时去，二是有矛盾的两个人不能同时

在场，所以先根据夫妻建边，然后根据具体的矛盾关系建边*/

#include<stdio.h>

#include<string.h>

#include<queue>

#include<stack>

#include<algorithm>

using namespace std;

#define MAX 100000+10

int low[MAX],dfn[MAX];

int head[MAX],sccno[MAX];

int scc_cnt,dfs_clock,cnt,m,n;

stack<int>s;

bool Instack[MAX];

struct node

{

	int u,v;

	int next;

}edge[MAX*2];

void init()

{

	cnt=0;

	memset(head,-1,sizeof(head));

}

void add(int u,int v)

{

	edge[cnt].u=u;

	edge[cnt].v=v;

	edge[cnt].next=head[u];

	head[u]=cnt++;

}

void getmap()

{//一对夫妻只能去一个人，所以分别建边，以为只有男女之分，所以4层就够了

	for(int i=0;i<n;i++)

	{

		add(i+3*n,i);

		add(i+2*n,i+n);

		add(i+n,i+2*n);

		add(i,i+3*n);

	}

	int a1,a2,c1,c2;

	while(m--)

	{//按照矛盾关系建边，女在偶数层，男在奇数层，第一组与第二组也有一些分别

		scanf("%d%d%d%d",&a1,&a2,&c1,&c2);

		if(c1==0&&c2==0)

		//四种关系0--0  1--1  1--0  0--1

		{

			add(a1,a2+2*n);

			add(a2,a1+2*n);

		}

		else if(c1==1&&c2==1)

		{

			add(a1+n,a2+3*n);

			add(a2+n,a1+3*n);

		}

		else if(c1==1&&c2==0)

		{

			add(a1+n,a2+2*n);

			add(a2,a1+3*n);

		}

		else

		{

			add(a1,a2+3*n);

			add(a2+n,a1+2*n);

		}

	 }

}

void tarjan(int u,int fa)

{

	int v;

	low[u]=dfn[u]=++dfs_clock;

	s.push(u);

	Instack[u]=true;

	for(int i=head[u];i!=-1;i=edge[i].next)

	{

		v=edge[i].v;

		if(!dfn[v])

		{

			tarjan(v,u);

			low[u]=min(low[u],low[v]);

		}

		else if(Instack[v])

		low[u]=min(low[u],dfn[v]);

	}

	if(dfn[u]==low[u])

	{

		scc_cnt++;

		for(;;)

		{

			v=s.top();

			s.pop();

			Instack[v]=false;

			sccno[v]=scc_cnt;

			if(v==u) break;

		}

	}

}

void find(int l,int r)

{

	memset(sccno,0,sizeof(sccno));

	memset(Instack,false,sizeof(Instack));

	memset(low,0,sizeof(low));

	memset(dfn,0,sizeof(dfn));

	scc_cnt=dfs_clock=0;

	for(int i=l;i<=r;i++)

	if(!dfn[i])

	tarjan(i,-1);

}

void solve()

{

	int flog=1;

	for(int i=0;i<2*n;i++)

	{

		if(sccno[i]==sccno[i+2*n])//如果有矛盾的两个人在一组

		{

			flog=0;

			printf("NO\n");

			break;

		}

	}

	if(flog)

	printf("YES\n");

}

int main()

{

	while(scanf("%d%d",&n,&m)!=EOF)

	{

		init();

		getmap();

		find(0,4*n-1);

		solve();

	}

	return 0;

}