Party

2 10 1 1 1  Sample Output
YES 
题目大意：
                  2-sat问题，详见博客：浅谈 2-SAT问题
题目思路：
                 对于这类问题一般的解法为将每个点分为 x 和 x' 分别表示每组当中的两种状态，这里表示丈夫和妻子，然后更具定义我们建图，如果 A和B有矛盾则选A必选B'，选B必选A' ，所以我们对该图缩点，如果A和A'属于同一个环当中则说明选A必选A'，所以不存在，否则就存在
AC代码：
#include<cstring>#include<cstdio>const int maxn = 3e3+20;int low[maxn],dfn[maxn],vis[maxn],belon[maxn],stack[maxn];int hed[maxn];int n,m,e,top,cnt,num;struct st{    int v,nex;}edge[maxn*maxn];void add(int u,int v){    edge[e].v=v,edge[e].nex=hed[u],hed[u]=e++;}void init(){    memset(dfn,0,sizeof(dfn));    memset(vis,0,sizeof(vis));    memset(hed,-1,sizeof(hed));    memset(belon,0,sizeof(belon));    e=num=cnt=top=0;}void targan(int u){     //targan缩点    low[u]=dfn[u]=++num;    stack[top++]=u;    vis[u]=1;    for(int i=hed[u];~i;i=edge[i].nex){        int v = edge[i].v;        if(!dfn[v]){            targan(v);            if(low[u]>low[v])low[u]=low[v];        }else if(vis[v]&&dfn[v]<low[u])low[u]=dfn[v];    }    if(low[u]==dfn[u]){        int x;        ++cnt;        do{            x =stack[--top];            vis[x]=0;            belon[x]=cnt;        }while(x!=u);    }}bool work(){    for(int i=0;i<2*n;i++)if(!dfn[i])targan(i);    for(int i=0;i<n;i++){        if(belon[i*2]==belon[i*2+1])return false;   //同一组的成环    }    return true;}int main(){    while(~scanf("%d",&n)){            scanf("%d",&m);            init();            for(int i=0;i<m;i++){                int a,b,c,d;scanf("%d%d%d%d",&a,&b,&c,&d);                a = a*2+c;                b = b*2+d;                add(a,b^1);     //选A必选B'                add(b,a^1);     //选B必选A'            }            if(work())printf("YES/n");            else printf("NO/n");    }    return 0;}
                     -