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
建图方法：



用 tarjan 算法求强连通，然后判断 b 和 b' 是否在同一个连通分量里面就好。


#include"stdio.h"

#include"string.h"

#include"queue"

#include"stack"

#include"iostream"

#include"stdlib.h"

#define M 2009

#define inf 999999999

using namespace std;

stack<int>q;

int head[M],dfn[M],low[M],use[M],belong[M];

int num,index,t,n;

struct st

{

    int u,v,next;

}edge[M*M];

void init()

{

    t=0;

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

}

void add(int u,int v)

{

    edge[t].u=u;

    edge[t].v=v;

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

    head[u]=t++;

}

void tarjan(int u)

{

    int i;

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

    q.push(u);

    use[u]=1;

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

    {

        int v=edge[i].v;

        if(!dfn[v])

        {

            tarjan(v);

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

        }

        else if(use[v])

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

    }

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

    {

        num++;

        int vv;

        do

        {

            vv=q.top();

            q.pop();

            use[vv]=0;

            belong[vv]=num;

        }while(vv!=u);

    }

}

void solve()

{

    num=index=0;

    int i;

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

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

    memset(use,0,sizeof(use));

    for(i=1;i<=2*n;i++)//注意2*n

    {

        if(!dfn[i])

        {

            tarjan(i);

        }

    }

}

int main()

{

    int m,a,b,c,d,i;

    while(scanf("%d",&n)!=-1)

    {

        scanf("%d",&m);

        init();

        while(m--)

        {

            scanf("%d%d%d%d",&a,&b,&c,&d);

            a++;

            b++;

            if(c==0&&d==0)

            {

                add(2*a-1,2*b);

                add(2*b-1,2*a);

            }

            if(c==1&&d==1)

            {

                add(2*a,2*b-1);

                add(2*b,2*a-1);

            }

            if(c==0&&d==1)

            {

                add(2*a-1,2*b-1);

                add(2*b,2*a);

            }

            if(c==1&&d==0)

            {

                add(2*a,2*b);

                add(2*b-1,2*a-1);

            }

        }

        solve();

        int flag=0;

        for(i=1;i<=n;i++)

        {

            if(belong[i*2]==belong[i*2-1])

            {

                flag++;

                break;

            }

        }

        if(flag)

            printf("NO\n");

        else

            printf("YES\n");

    }

}