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

分析

本题是2-SAT问题，总体来讲比较简单，是模板题。
设现有编号为A、B的夫妻，$A_0$表示A夫妻的妻子 ，$B_1$是B夫妻的丈夫。注意到，

如果$A0$ 与$B1$ 有矛盾，则暗示

$A_0 -> B_0 并且 B_1 -> A_1$

即，每给出一对矛盾，对应着两条边。
依照以上的推理，类似的将题目给出的m条分别转换成两条边，进行建边。建边的规则遵照 李煜东 进阶指南 的方法。
最后注意，本题是多组测试数据，题目没有本身具体说明。

C++

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std ;

const int N = 2010 , M =2e6+10 ;

int n , m ; 
int h[N] , e[M] , ne[M] , idx  ;
int dfn[N] , low[N] , ts ;
int stk[N] , top;
int in_stk[N] ;
int id[N] , scc ;


void add(int a , int b) 
{
    e[idx] = b , ne[idx] = h[a] , h[a] = idx ++ ;     
}


void tarjan(int u ) 
{
    low[u] = dfn[u] = ++ts ;
    in_stk[u] = 1 , stk[top++] = u ;

    for(int i = h[u] ;  ~i ; i = ne[i]) 
    {
        int j = e[i] ;
        if(!dfn[j]) 
        {
            tarjan(j) ;
            low[u] = min(low[u] , low[j]) ;
        }
        else if(in_stk[j]) low[u] = min(low[u] , dfn[j] ) ;
    }

    if(low[u] == dfn[u]) 
    {
        scc ++ ;
        int y ;
        do
        {
            y = stk[--top] ;
            in_stk[y] = 0 ;
            id[y] = scc ; 
        }while(y != u ) ; 
    }

}


void init()
{
     memset(h , -1 , sizeof h) ;  
     memset(e , 0 , sizeof e) ;  
     memset(ne , 0 , sizeof ne) ;  
     memset(dfn , 0 , sizeof dfn) ;  
     memset(low , 0 , sizeof low) ;  
     memset(id , 0 , sizeof id) ;  
     memset(stk , 0 , sizeof stk) ;  
     memset(in_stk , 0 , sizeof in_stk) ;
     scc = top = ts = 0 ;
}

int main() 
{
    while(~scanf("%d%d",&n,&m))
    {
        init() ;
        while(m --) 
        {
            int i , a , j , b  ;
            scanf("%d%d%d%d",&i,&j,&a,&b) ;
            add( i + a * n , j + !b * n ) ;
            add( j + b * n , i + !a * n );
        }

        for(int i = 0 ; i < n *2 ; i ++ ) 
        {
            if(!dfn[i]) tarjan(i) ;
        }

        bool f =1 ;
        for(int i = 0 ; i < n ; i ++ ) 
        {
            if(id[i] == id[i+n]) 
            {
                f = 0 ;
                break ;
            }
        }
        if(f) puts("YES") ;
        else puts("NO") ;
    }

    return 0 ;
}