传送门：Party
题意：有n对夫妻被邀请参加一个聚会，因为场地的问题，每对夫妻中只有1人可以列席。在2n 个人中，某些人之间有着很大的矛盾（当然夫妻之间是没有矛盾的），有矛盾的2个人是不会同时出现在聚会上的。有没有可能会有n 个人同时列席？
分析：two-sat裸题，对于有仇恨的两对夫妻u，v，连边u->v'和v->u'；建好图直接tarjan缩点判断每对夫妻[i,i']是否属于一个强连通块内即可。
#include <cstdio>
#include <cstring>
#include <string>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <queue>
#include <cstdlib>
#include <stack>
#include <vector>
#include <set>
#include <map>
#define LL long long
#define mod 100000000
#define inf 0x3f3f3f3f
#define eps 1e-6
#define N 2010
#define FILL(a,b) (memset(a,b,sizeof(a)))
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define PII pair<int,int>
using namespace std;
struct edge
{
int v,next;
edge() {}
edge(int v,int next):v(v),next(next) {}
} e[N*N/];
int n,m,scc,step,top,tot;
int head[N],dfn[N],low[N],belong[N],Stack[N];
bool instack[N];
void init()
{
tot=;step=;
scc=;top=;
FILL(head,-);
FILL(dfn,);
FILL(low,);
FILL(instack,false);
}
void addedge(int u,int v)
{
e[tot]=edge(v,head[u]);
head[u]=tot++;
}
void tarjan(int u)
{
int v;
dfn[u]=low[u]=++step;
Stack[top++]=u;
instack[u]=true;
for(int i=head[u]; ~i; i=e[i].next)
{
v=e[i].v;
if(!dfn[v])
{
tarjan(v);
low[u]=min(low[u],low[v]);
}
else if(instack[v])
{
low[u]=min(low[u],dfn[v]);
}
}
if(dfn[u]==low[u])
{
scc++;
do
{
v=Stack[--top];
instack[v]=false;
belong[v]=scc;
}
while(v!=u);
}
} void solve()
{
for(int i=; i<*n; i++)
if(!dfn[i])tarjan(i);
bool flag=true;
for(int i=; i<n; i++)
{
if(belong[i<<]==belong[i<<^])
{
flag=false;
break;
}
}
if(flag)puts("YES");
else puts("NO");
}
int main()
{
int a,b,u,v;
while(scanf("%d%d",&n,&m)>)
{
init();
for(int i=;i<=m;i++)
{
scanf("%d%d%d%d",&a,&b,&u,&v);
addedge(*a+u,*b+v^);
addedge(*b+v,*a+u^);
} solve();
}
}