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
每对夫妻只能夫去妻不去或反之两种情况设为i和i'
注意四点：一是kosaraju的dfs序是出栈序列
二是使用乘积表示可能出现一个点表示两重含义,采取加法偏移更容易处理
三是注意vis数组的标记的对象
四是要求到场n个人,夫妻两个不能一个都不到场
点击查看代码
#include<bits/stdc++.h>
using namespace std;
const int N=2e3+10;
const int M=4e6+10;
int e[M],ne[M],h[N],idx;
int ce[M],cne[M],ch[N],cidx;
int vis[N],f[N],q[N],cnt;
void add(int u,int v)
{
e[++idx]=v;
ne[idx]=h[u];
h[u]=idx;
}
void cadd(int u,int v)
{
ce[++cidx]=v;
cne[cidx]=ch[u];
ch[u]=cidx;
}
void dfs1(int x)
{
vis[x]=1;
for(int i=h[x];~i;i=ne[i])
{
int j=e[i];
if(!vis[j]) dfs1(j);
}
q[++cnt]=x;
}
void dfs2(int x,int y)
{
vis[x]=0;f[x]=y;
for(int i=ch[x];~i;i=cne[i])
{
int j=ce[i];
if(vis[j]) dfs2(j,y);
}
}
void solve(int n,int m)
{
//因为第i对夫妻只有夫去或妻去两种情况,用i来表示夫去,i+T表示妻去
memset(h,-1,sizeof h);
memset(ch,-1,sizeof ch);
idx=0;cidx=0;cnt=0;
int T=n;
for(int i=0;i<m;++i)
{
int a1,a2,c1,c2;
cin>>a1>>a2>>c1>>c2;
a1++;a2++;
//用a1+c1*T若为夫则值为a1,若为妻则值为a1+T
//用(a1+c1*T+T)%2*T表示否定,若为夫值为a1+T,若为妻值为a1
add(a1+c1*T,(a2+c2*T+T)%(2*T));
add(a2+c2*T,(a1+c1*T+T)%(2*T));
cadd((a2+c2*T+T)%(2*T),a1+c1*T);
cadd((a1+c1*T+T)%(2*T),a2+c2*T);
}
for(int i=1;i<=2*n;++i) if(!vis[i]) dfs1(i);
for(int i=2*n;i;--i) if(vis[q[i]]) dfs2(q[i],q[i]);
bool flag=1;
for(int i=1;i<=n;++i) if(f[i]==f[i+T]) flag=0;
if(flag) cout<<"YES"<<'\n';
else cout<<"NO"<<'\n';
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int n,m;
while(cin>>n>>m)
{
solve(n,m);
}
}