推荐论文：https://blog.csdn.net/zixiaqian/article/details/4492926

2-SAT问题是2判定性问题，给出n个集合，每个集合中有两个元素，两个元素之一要出现，且有一些元素不能相互共存

考虑每个集合中的元素都为i 和 i'，对于每组信息在他们之间连边，连上边就绑定啦，它们一定要一起选

如果有一个点必须选又必须不选，就是矛盾

有N对物品，每对物品中必须选取一个，也只能选取一个，并且它们之间存在某些限制关系

2-sat中一条有向边的涵义是选了起点就必须选终点

模板：solve表示能否按规则取出，vis中标记为1的元素即为最终取出的元素

bool dfs(int u)
{
if(vis[u]) return true;
if(vis[u^]) return false;
s[cnt++] = u;
vis[u] = ;
for(int i = head[u];i;i = nxt[i])
{
int v = l[i];
if(!dfs(v))
return false;
}
return true;
}
bool solve()
{
for(int i = ; i < n; i++)
{
if(!vis[i<<] && !vis[i<<|])
{
cnt = ;
if(!dfs(i<<))
{
while(cnt) vis[s[--cnt]] = false;
if(!dfs(i<<|)) return false;
}
}
}
return true;
}

HDU 1814

题意：n个党派要参加会议，每个党派有两个人，要派出一个人去参加，有些人不能同时去，求输出字典序最小的方案

思路：裸题，要求字典序最小就从前面开始搜就可以了

#include
#include
#include
#include
#include
#include
#include
using namespace std;
const int maxn = ;
const int maxm = ;
const int INF = ;
int head[maxm], nxt[maxm], l[maxm], tot = ;
void build(int f, int t)
{
l[++tot] = t;
nxt[tot] = head[f];
head[f] = tot;
}
int n, m, cnt, vis[maxn], s[maxn];
void init()
{
memset(head, , sizeof(head));
tot = ;
memset(vis, , sizeof(vis));
}
bool dfs(int u)
{
if(vis[u]) return true;
if(vis[u^]) return false;
s[cnt++] = u;
vis[u] = ;
for(int i = head[u];i;i = nxt[i])
{
int v = l[i];
if(!dfs(v))
return false;
}
return true;
}
bool solve()
{
for(int i = ; i < n; i++)
{
if(!vis[i<<] && !vis[i<<|])
{
cnt = ;
if(!dfs(i<<))
{
while(cnt) vis[s[--cnt]] = false;
if(!dfs(i<<|)) return false;
}
}
}
return true;
}
int main()
{
while(~scanf("%d %d", &n, &m))
{
init();
for(int i = ; i < m; i++)
{
int a, b;
scanf("%d %d", &a, &b);
build(a-, (b-)^);
build(b-, (a-)^);
}
if(solve())
{
for(int i = ; i < n; i++)
{
if(vis[i<<]) printf("%d\n", i<<|);
else printf("%d\n", (i<<)+);
}
}
else printf("NIE\n");
}
return ;
}

POJ 3648

题意：有n-1对夫妇参加新娘新郎的婚礼，每对夫妇要坐对面，且有些对有（奸情）的不能同时坐在新娘的对面，问新娘这一侧都坐了谁

思路：看起来就是2-SAT问题，每一对夫妇是一个集合

因为新娘这一侧是可以有冲突的！！所以要考虑我们求新娘对面都坐了谁

这样的话我们就不能选新娘

连一条新娘向新郎的边，如果选了新娘，那么就要选新郎，就产生冲突了，判为不行

思路好神奇哇

#include
#include
#include
#include
#include
#include
#include
using namespace std;
const int maxn = ;
const int maxm = ;
const int INF = ;
int head[maxm], nxt[maxm], l[maxm], tot = ;
void build(int f, int t)
{
l[++tot] = t;
nxt[tot] = head[f];
head[f] = tot;
}
int n, m, cnt, vis[maxn], s[maxn];
void init()
{
memset(head, , sizeof(head));
tot = ;
memset(vis, , sizeof(vis));
}
bool dfs(int u)
{
if(vis[u]) return true;
if(vis[u^]) return false;
s[cnt++] = u;
vis[u] = ;
for(int i = head[u];i;i = nxt[i])
{
int v = l[i];
if(!dfs(v))
return false;
}
return true;
}
bool solve()
{
for(int i = ; i < n; i++) { if(!vis[i<<] && !vis[i<<|]) { cnt = ; if(!dfs(i<<)) { while(cnt) vis[s[--cnt]] = false; if(!dfs(i<<|)) return false; } } } return true; } int cal(int x, char c) { if(c == 'h') return x<<; if(c == 'w') return x<<|; } int main() { while() { scanf("%d %d", &n, &m); if(n == && m == ) break; init(); for(int i = ; i < m; i++) { int a, b; char c, d; scanf("%d%c%d%c", &a, &c, &b, &d); a = cal(a, c); b = cal(b, d); build(a, b^); build(b, a^); } build(, ); if(solve()) { for(int i = ; i < n; i++) { if(i > ) printf(" ");
printf("%d", i);
if(vis[i<<]) printf("w");
else printf("h");
}
printf("\n");
}
else printf("bad luck\n");
}
return ;
}

题意：0 ~ n-1这n个数，给出两个数之间AND OR 或者 XOR的值，问能否推断出这几个数都是什么

思路：n个数对应n个集合，每个数为0或1对应一个集合中的i 和 i'，

a and b == 1, 这种情况a和b必须取1，所以连边a’->a, b’->b.
a and b == 0, 这种情况a和b不能同时为1，所以连边a->b’, b->a’.
a or b == 1, 这种情况a和b不能同时为0，所以连边a’->b, b’->a.
a or b == 0, 这种情况a和b必须同时为0，所以连边a->a’, b->b’.
a xor b == 1, 这种情况a和b取值要相反，所以连边a->b’, a’->b, b->a’, b’->a.
a xor b == 0, 这种情况a和b取值要相同，所以连边a->b, b->a, a’->b’, b’->a’.

也可以这么想：

x,y代表当前的式子未知数..x0为x选0的点..x1为x选1的点…y0,y1同样..

1、x AND y = 1 .. 表明x , y必须为1…所以不能选择x0,y0…这个东西要表示出来..就让选择x0,y0直接就自我矛盾..加边 ( x0,x1 ) , ( y0,y1 )

2、x AND y = 0 ..表明x,y至少有一个为0…那么加边 ( x1,y0 ) , ( y1,x0 )

3、x OR y = 1 …表明x,y至少有一个味1..那么加边 ( x0,y1 ) , ( y0,x1 )

4、x OR y = 0..表明x,y都为0…所以让选择x1,y1就直接自矛盾 ( x1,x0 ) , ( y1,y0 )

5、x XOR y = 1..表明x,y不同..那么加边 ( x0,y1 ) , ( x1,y0 ) ,( y0,x1 ) , ( y1,x0 )

6、x XOR y = 0..表明x,y是相同的..那么加边 ( x0,y0 ) , ( x1,y1 ) ,( y0,x0 ) , ( y1,x1 )

tarjan看一个集合中的两个点是不是在同一个环里，在的话就凉凉

主要还是在于建图

#include
#include
#include
#include
#include
#include
#include
using namespace std;
const int SZ = ;
const int INF = ;
int head[SZ], nxt[SZ], l[SZ], tot = ;
void build(int f, int t)
{
l[++tot] = t;
nxt[tot] = head[f];
head[f] = tot;
}
int n, m;
stack s;
int dfn[], low[], clock = ;
int sccnum[], cnt = ;
void dfs(int u)
{
dfn[u] = low[u] = ++clock;
s.push(u);
for(int i = head[u]; i; i = nxt[i])
{
int v = l[i];
if(!dfn[v])
{
dfs(v);
low[u] = min(low[u], low[v]);
}
else if(!sccnum[v])
low[u] = min(low[u], dfn[v]);
}
if(low[u] == dfn[u])
{
cnt++;
while()
{
int v = s.top();
s.pop();
sccnum[v] = cnt;
if(u == v) break;
}
}
}
void tarjan()
{
for(int i = ; i < n<<; i++)
if(!dfn[i]) dfs(i);
}
void init()
{
memset(head, , sizeof(head));
tot = ;
memset(dfn, , sizeof(dfn));
memset(low, , sizeof(low));
clock = ;
while(s.size()) s.pop();
cnt = ;
memset(sccnum, , sizeof(sccnum));
}
int main()
{
while(~scanf("%d %d", &n, &m))
{
init();
for(int i = ; i < m; i++)
{
int a, b, c;
char op[];
scanf("%d%d%d%s", &a, &b, &c, op);
if(op[] == 'A')
{
if(c == ) build(a<<|, a<<), build(b<<|, b<<);
if(c == ) build(a<<, b<<|), build(b<<, a<<|);
}
if(op[] == 'O')
{
if(c == ) build(a<<|, b<<), build(b<<|, a<<);
if(c == ) build(a<<, a<<|), build(b<<, b<<|);
}
if(op[] == 'X')
{
if(c == ) build(a<<, b<<|), build(a<<|, b<<), build(b<<, a<<|), build(b<<|, a<<);
if(c == ) build(a<<, b<<), build(b<<, a<<), build(a<<|, b<<|), build(b<<|, a<<|);
}
}
tarjan();
bool flag = true;
for(int i = ; i < n; i++)
if(sccnum[i<<] == sccnum[i<<|]) flag = false;
if(flag) printf("YES\n");
else printf("NO\n");
}
return ;
}

POJ 3207

题意：一个圈上顺着排0,1,…,n-1号点，给出m条边，每条边可以从圆内走也可以从圆外走，问这些边可不可以不相交

思路：对于每条Link，要么在圆外，要么在圆内，且不可同时满足，只能两者取一，判断这M条Link是否合法，也就是M条Link不冲突，这就是典型的2-sat问题了。

将每条Link i 看做一个点，如果Link在圆内，则选做i ，如果在圆外， 则选做i'。对于两条线(i,j) ，如果i，j不能同时在圆内，也就可以推出两者不能同时在圆外

如果这两条边冲突，那么balabala连边

构图方式神奇↓

#include
#include
#include
#include
#include
#include
#include
using namespace std;
const int maxn = ;
const int maxm = ;
const int INF = ;
int head[maxm], nxt[maxm], l[maxm], tot = ;
struct Edge
{
int f, t;
}e[];
void build(int f, int t)
{
l[++tot] = t;
nxt[tot] = head[f];
head[f] = tot;
}
int n, m, cnt, vis[maxn], s[maxn];
void init()
{
memset(head, , sizeof(head));
tot = ;
memset(vis, , sizeof(vis));
}
bool dfs(int u)
{
if(vis[u]) return true;
if(vis[u^]) return false;
s[cnt++] = u;
vis[u] = ;
for(int i = head[u]; i; i = nxt[i])
{
int v = l[i];
if(!dfs(v))
return false;
}
return true;
}
bool solve()
{
for(int i = ; i < m; i++) { if(!vis[i<<] && !vis[i<<|]) { cnt = ; if(!dfs(i<<)) { while(cnt) vis[s[--cnt]] = false; if(!dfs(i<<|)) return false; } } } return true; } int main() { scanf("%d %d", &n, &m); for(int i = ; i < m; i++) { int a, b; scanf("%d%d", &a, &b); e[i].f = min(a, b); e[i].t = max(a, b); } for(int i = ; i < m; i++) for(int j = i+; j < m; j++) if((e[j].fe[i].f) || (e[j].f>e[i].f && e[j].fe[i].t))
{
build(i<<, j<<|);
build(j<<, i<<|);
build(i<<|, j<<);
build(j<<|, i<<);
}
if(solve()) printf("panda is telling the truth…\n");
else printf("the evil panda is lying again\n");
return ;
}