Problem Description
有n对夫妻被邀请参加一个聚会，因为场地的问题，每对夫妻中只有1人可以列席。在2n 个人中，某些人之间有着很大的矛盾（当然夫妻之间是没有矛盾的），有矛盾的2个人是不会同时出现在聚会上的。有没有可能会有n 个人同时列席？
Input
n： 表示有n对夫妻被邀请 (n<= 1000)
m： 表示有m 对矛盾关系 ( m < (n - 1) * (n -1))
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
否则输出 NO
Sample Input
2 1 0 1 1 1
Sample Output
YES
Source
Recommend
lcy
由于题目问题。知道n对夫妻要上N个人。也就是每对夫妻出一个人。
可以这么说。给出一条矛盾关系
如果是 i,j,0,0 ，可以连有向边 i0->j1,j0->i1 若出来i0，则必须出来j1.类推
如果是 i,j,0,1 , 可以连有向边 i0->j0,j1->i1
如果是 i,j,1,0 , 可以连有向边 i1->j1,j0->i0
如果是 i,j,1,1 , 可以连有向边 i1->j0,j1->i0
如此就建好了一个所有有约束关系的有向图了，由于只是一个判定性问题，只需在这样建立的有向图上运行一次强连通算法，最后再判定所有的i0,j0是否存在于一个强连通分量即可。
/*
* @author ipqhjjybj
* @date 20130702
*
*/
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <numeric>
#include <utility>
#include <cstring>
#include <vector>
#include <stack>
#include <queue>
#include <map>
#include <string>
using namespace std;
#define inf 0x3f3f3f3f
#define MAXN 2005
#define clr(x,k) memset((x),(k),sizeof(x))
#define clrn(x,k) memset((x),(k),(n+1)*sizeof(int))
#define cpy(x,k) memcpy((x),(k),sizeof(x))
#define Base 10000
typedef vector<int> vi;
typedef stack<int> si;
typedef vector<string> vs;
#define sz(a) int((a).size())
#define pb push_back
#define all(c) (c).begin(),(c).end()
#define rep(i,n) for(int i = 0;i < n;++i)
#define foreach(it,c) for(vi::iterator it = (c).begin();it != (c).end();++it)
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
vector<int> vec[MAXN];
int n,m;
int id[MAXN],pre[MAXN],low[MAXN],s[MAXN],stop,cnt,scnt;
void init(){
int u,v;
for(int i = 0;i < n+n;i++) vec[i].clear();
for(int i = 0,a,b,c,d;i < m;i++){
scanf("%d %d %d %d",&a,&b,&c,&d);
u = (a<<1) + c ; v = (b<<1) + d;
vec[u].push_back(v^1);
vec[v].push_back(u^1);
}
stop=cnt=scnt=0;
clr(pre,-1);
clr(id,0);
}
void Tarjan(int v,int n){
int t,minc=low[v]=pre[v]=cnt++;
vector<int>::iterator pv;
s[stop++]=v;
for(pv=vec[v].begin();pv!=vec[v].end();++pv){
if(-1==pre[*pv]) Tarjan(*pv,n);
if(low[*pv] < minc) minc=low[*pv];
}
if(minc<low[v]){
low[v]=minc;return;
}do{
id[t=s[--stop]]=scnt;low[t]=n;
}while(t!=v);
++scnt;
}
int main(){
// freopen("3062.in","r",stdin);
int i;
while(scanf("%d",&n)!=EOF&&n){
scanf("%d",&m);
init();
for(i = 0;i < n+n;i++)
if(-1==pre[i])
Tarjan(i,n+n);
//以下进行判断
bool flag = true;
for(i=0;i<n;i++)
if(id[i<<1]==id[(i<<1)^1]){
flag=false;
break;
}
if(flag)
printf("YES\n");
else printf("NO\n");
}
return 0;
}