2-SAT的入门题。
a,a',b,b'分别表示两对夫妇,如果a,b有矛盾,那么a要来,就只能来b',b要来,就只能来a'。于是建了两条边(a,b'),(b,a')。
用tarjan强连通分量缩点染色后,如果同一对夫妇染色相同,说明两个要么都来,要么都不来,就不可能有解了。否则,形成的强连通分量中必定是对称的(abc是强连通分量,那么a'b'c'也会在一个强连通分量里),于是只要选择几个强连通分量就可以每个集合都选1个。
#include <cstdio>
#include <cstring>
const int N=2001;
const int M=4000010;
struct Edge
{
int to,next;
}edge[M];
int head[N],tot;
int Low[N],DFN[N],Stack[N],Belong[N];
int Index,top;
int scc;
bool Instack[N];
void addedge(int u,int v)
{
edge[tot].to = v;edge[tot].next = head[u];head[u] = tot++;
}
void Tarjan(int u)
{
int v;
Low[u] = DFN[u] = ++Index;
Stack[top++] = u;
Instack[u] = true;
for(int i = head[u];~i;i = edge[i].next)
{
v = edge[i].to;
if( !DFN[v] )
{
Tarjan(v);
if(Low[u] > Low[v])Low[u] = Low[v];
}
else if(Instack[v] && Low[u] > DFN[v])
Low[u] = DFN[v];
}
if(Low[u] == DFN[u])
{
scc++;
do
{
v = Stack[--top];
Instack[v] = false;
Belong[v] = scc;
}
while( v != u);
}
}
void solve(int n)
{
memset(DFN,0,sizeof(DFN));
memset(Instack,false,sizeof Instack);
Index = scc = top = 0;
for(int i = 0;i < n*2;i++)
if(!DFN[i])
Tarjan(i);
int ok=1;
for(int i=0;i<n&&ok;i++)
if(Belong[i*2]==Belong[i*2+1])
ok=0;
if(ok)
puts("YES");
else
puts("NO");
}
void init()
{
tot = 0;
memset(head,-1,sizeof head);
}
int main()
{
int n,m;
int a1,a2,c1,c2;
while(~scanf("%d%d",&n,&m))
{
init();
while(m--)
{
scanf("%d%d%d%d",&a1,&a2,&c1,&c2);
addedge(a1*2+c1,a2*2+1-c2);
addedge(a2*2+c2,a1*2+1-c1);
}
solve(n);
}
return 0;
}