Problem Description
小时候，乡愁是一枚小小的邮票，我在这头，母亲在那头。
—— 余光中
集训是辛苦的，道路是坎坷的，休息还是必须的。经过一段时间的训练，lcy决定让大家回家放松一下，但是训练还是得照常进行，lcy想出了如下回家规定，每一个队（三人一队）或者队长留下或者其余两名队员同时留下；每一对队员，如果队员A留下，则队员B必须回家休息下，或者B留下，A回家。由于今年集训队人数突破往年同期最高记录，管理难度相当大，lcy也不知道自己的决定是否可行，所以这个难题就交给你了，呵呵，好处嘛~，免费**漂流一日。
Input
第一行有两个整数，T和M，1<=T<=1000表示队伍数，1<=M<=5000表示对数。
接下来有T行，每行三个整数，表示一个队的队员编号，第一个队员就是该队队长。
然后有M行，每行两个整数，表示一对队员的编号。
每个队员只属于一个队。队员编号从0开始。
Output
可行输出yes，否则输出no，以EOF为结束。
Sample input
1 2
0 1 2
0 1
1 2
2 4
0 1 2
3 4 5
0 3
0 4
1 3
1 4
Sample output
yes
no
图论-2—SAT
本题注意逆否命题边的建立
点击查看代码
#include<bits/stdc++.h>
using namespace std;
const int N=3e4;
int h[N],e[N],ne[N],idx;
int ch[N],ce[N],cne[N],cidx;
int f[N],vis[N],q[N],cnt;
void add(int u,int v)
{
e[++idx]=v;
ne[idx]=h[u];
h[u]=idx;
}
void cadd(int v,int u)
{
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);
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int n,m;
while(cin>>n>>m)
{
int T=3*n;
memset(h,-1,sizeof h);
memset(ch,-1,sizeof ch);
idx=0,cnt=0;cidx=0;
for(int i=1;i<=n;++i)
{
int a,b,c;
cin>>a>>b>>c;
a++;b++;c++;
add(a,b+T);add(a,c+T);
add(a+T,b);add(a+T,c);
add(b,a+T);add(b,c);
add(b+T,c+T);add(b+T,a);
add(c,a+T);add(c,b);
add(c+T,b+T);add(c+T,a);
cadd(a,b+T);cadd(a,c+T);
cadd(a+T,b);cadd(a+T,c);
cadd(b,a+T);cadd(b,c);
cadd(b+T,c+T);cadd(b+T,a);
cadd(c,a+T);cadd(c,b);
cadd(c+T,b+T);cadd(c+T,a);
}
for(int i=0;i<m;++i)
{
int a,b;
cin>>a>>b;
a++;b++;
add(a,b+T);add(b,a+T);
cadd(a,b+T);cadd(b,a+T);
}
for(int i=1;i<=n*6;++i)
{
if(!vis[i]) dfs1(i);
}
for(int i=n*6;i;--i)
{
if(vis[q[i]]) dfs2(q[i],q[i]);
}
bool ans=1;
for(int i=1;i<=n*3;++i)
{
if(f[i]==f[i+T])
ans=0;
}
if(ans) cout<<"yes"<<'\n';
else cout<<"no"<<'\n';
}
}