这道题是我对于2-SAT问题的入门题：http://poj.org/problem?id=3207
一篇非常非常非常好的博客,很详细,认真看一遍差不多可以了解个大概：https://blog.csdn.net/JarjingX/article/details/8521690
总结一下我对于 2-SAT 问题的初步见解：
有很多个集合，每个集合里面有若干元素，现给出一些取元素的规则，要你判断是否可行，可行则给出一个可行方案。如果所有集合中，元素个数最多的集合有k个，那么我们就说这是一个k-sat问题，同理，2-sat问题就是k=2时的情况。
通常我们需要将集合中点之间的边转化成点, 再将点转化成多条新边, 这些新边就要看问题是属于哪类模型。
模型一：两者（A，B）不能同时取
那么选择了A就只能选择B’，选择了B就只能选择A’
连边A→B’，B→A’
模型二：两者（A，B）不能同时不取
那么选择了A’就只能选择B，选择了B’就只能选择A
连边A’→B，B’→A
模型三：两者（A，B）要么都取，要么都不取
那么选择了A，就只能选择B，选择了B就只能选择A，选择了A’就只能选择B’，选择了B’就只能选择A’
连边A→B，B→A，A’→B’，B’→A’
模型四：两者（A，A’）必取A
连边A’→A
题目大意：
一个圆环上有n个点, 点的序号从 0 到 n - 1, 给出m条边,说明点a, b之间有一条边相连接, 这条边可以在圆内部,也可以在圆的外部, 但边与边之间不能相交。求是否有满足的情况。
解题思路：
设对于一条边,在圆内部连接为i,圆外部连接为 i',那么两条理论上相交的边i, j（通过两条边的左右坐标来判断是否相交）,就不能同时选择在圆的同一边。也就是模型一：两者（A, B）不能同时选。
注意的是 i'只是区别于i的一条对立边, 但是这条对立边不能影响到原来所存在的边, 这里我们可以用 i + m来表示 i 的对立边。
所以我们加边为 ,add(i,j + m), add(i + m, j), add(j, i + m), add(j + m, i)
然后再对 2 * m 个点（包括对立点）进行tarjan, 最后判断 m 个原始边的对立边是否处在同一个强连通分量中, 若存在处在同一个强连通分量中的,则无解,否则有解。
代码：
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<stack>
#define mem(a, b) memset(a, b, sizeof(a))
using namespace std; int n, m; //n个点, m条边 ,点是从 0 到 n - 1
int l[], r[];
int cnt, head[];
int dfn[], low[], vis[], deep, color, belong[];
stack<int>S; void init()
{
mem(head, -);
cnt = ;
mem(dfn, );
mem(low, );
mem(vis, );
mem(belong, );
deep = ;
color = ;
} struct Edge
{
int to, next;
int from;
}edge[ * * ]; //要注意这个边的数量 void add(int a, int b)
{
edge[++ cnt].to = b;
edge[cnt].next = head[a];
head[a] = cnt;
} void tarjan(int now)
{
dfn[now] = low[now] = ++ deep;
vis[now] = ;
S.push(now);
for(int i = head[now]; i != -; i = edge[i].next)
{
int to = edge[i].to;
if(!dfn[to])
{
tarjan(to);
low[now] = min(low[now], low[to]);
}
else if(vis[to])
low[now] = min(low[now], dfn[to]);
}
if(dfn[now] == low[now])
{
color ++;
while()
{
int temp = S.top();
S.pop();
vis[temp] = ;
belong[temp] = color;
if(temp == now)
break;
}
}
} int main()
{
int flag = ;
init();
scanf("%d%d", &n, &m);
for(int i = ; i <= m; i ++)
{
int a, b;
scanf("%d%d", &a, &b);
if(a > b)
swap(a, b);
l[i] = a, r[i] = b;//记录每条边的左端点和右端点,保证左小右大
}
for(int i = ; i < m; i ++) //建 2-SAT 图,将边转化成点处理
{ // A B不能同时存在的模型
for(int j = i + ; j <= m; j ++) //理论上有相交的边就转化成点来构造 2-SAT 问题的边
{
if(l[i] <= l[j] && r[i] >= l[j] && r[i] <= r[j] || l[i] >= l[j] && r[i] >= r[j] && l[i] <= r[j])
{
add(i, j + m);
add(i + m, j);
add(j, i + m);
add(j + m, i);
}
}
}
for(int i = ; i <= * m; i ++)//对于 i 边,其对立边为 i + m.每条边被看成点, 即总共有 2 * m个点
if(!dfn[i])
tarjan(i);
for(int i = ; i <= m; i ++)//点与对立点不能同时存在一个强连通分量中, 否则问题无解
{
int x = belong[i], y = belong[i + m];
if(x == y)
{
flag = ;
break;
}
}
if(flag)
printf("panda is telling the truth...\n");
else
printf("the evil panda is lying again\n");
return ;
}