看了下2-SAT，然后随便水了两道题

POJ3207 这个段哥当时讲过，然而我当时十分Naive。。

这题良心到Tarjan都不用写直接写个BCJ就好了因为连边的特殊性

#include <iostream>
#include <cstring>
#include <cmath>
#include <cstdio>
#include <algorithm>
using namespace std;
#define N 1050
int n,m,ln[N][2],fa[N],ri,ss=1,st=0,ans=0;
inline int Read()
 {
 	int x=0;char y;
 	do y=getchar(); while (y<'0'||y>'9');
 	do x=x*10+y-'0',y=getchar(); while (y>='0'&&y<='9');
 	return x;
 }
inline bool Intersect(int x,int y)
 {return ln[x][0]>ln[y][0]&&ln[x][0]<ln[y][1]&&ln[x][1]>ln[y][1];}
int Find(int x)
 {return fa[x]==x?x:(fa[x]=Find(fa[x]));}
int main()
 {
 	n=Read();m=Read();
 	for (int i=1;i<=m;i++)
 	 {
 	    ln[i][0]=Read();ln[i][1]=Read();fa[i]=i;fa[i+m]=i+m;
 	    if (ln[i][0]>ln[i][1]) swap(ln[i][0],ln[i][1]);
 	 }
 	for (int i=1;i<m;i++)
 	 for (int j=i+1;j<=m;j++)
 	  if (Intersect(i,j)||Intersect(j,i))
 	    fa[Find(i)]=Find(j+m),fa[Find(i+m)]=Find(j);
 	for (int i=1;i<=m;i++)
 	 if (Find(i)==Find(i+m)) {ans=-1;break;}
 	if (ans) puts("the evil panda is lying again");else
 	  puts("panda is telling the truth...");
 	return 0;
 }

POJ3678

Tarjan然后求个强连通分量，如果i和i'在同一强连通分量内就肯定是无解的。

至于怎么证并不知道= =，而且这题还没有对称性

#include <iostream>
#include <cstring>
#include <cmath>
#include <cstdio>
#include <algorithm>
using namespace std;
#define N 2050
#define M 3000050
int fi[N],c[M][2],low[N],n,m,ss,ri,li[N],cl[N],st,ln[M][2];
int s[N];bool b[N];char d[20];
inline int Read()
 {
 	int x=0;char y;
 	do y=getchar(); while (y<'0'||y>'9');
 	do x=x*10+y-'0',y=getchar(); while (y>='0'&&y<='9');
 	return x;
 }
inline void Line(int x,int y)
 {c[++ss][0]=y;c[ss][1]=fi[x];fi[x]=ss;ln[ss][0]=x;ln[ss][1]=y;}
void DFS(int x,int y)
 {
 	int k=++ri;li[ri]=x;low[x]=y;b[x]=1;
 	for (int i=fi[x];i;i=c[i][1])
 	 if (b[c[i][0]])
 	   low[x]=min(low[x],low[c[i][0]]);else
 	 if (!low[c[i][0]])
 	   DFS(c[i][0],y+1),low[x]=min(low[x],low[c[i][0]]);
 	if (low[x]==y)
 	 {
 	 	st++;
 	 	for (int i=k;i<=ri;i++)
 	 	  b[li[i]]=0,cl[li[i]]=st;
 	 	ri=k-1;
 	 }
 }
int main()
 {
 	n=Read();m=Read();
 	for (int i=1;i<=m;i++)
 	 {
 	 	int q=Read()+1,w=Read()+1,e=Read();
 	 	scanf("%s",d);
 	 	if (d[0]=='A'&&!e)
 	 	  Line(q,w+n),Line(w,q+n);else
 	 	if (d[0]=='A')
 	 	  Line(q+n,q),Line(w+n,w);else
 	 	if (d[0]=='O'&&!e)
 	 	  Line(q,q+n),Line(w,w+n);else
 	 	if (d[0]=='O')
 	 	  Line(q+n,w),Line(w+n,q);else
 	 	if (e)
 	 	  Line(q+n,w),Line(q,w+n),Line(w,q+n),Line(w+n,q);else
 	 	  Line(q,w),Line(w,q),Line(q+n,w+n),Line(w+n,q+n);
 	 }
 	for (int i=1;i<=n*2;i++)
 	 if (!low[i]) DFS(i,1);
 	for (int i=1;i<=n;i++)
 	 if (cl[i]==cl[i+n])
 	  {puts("NO");return 0;}
 	puts("YES");
 	return 0;
 }

还有输出字典序最小解的就是暴力O(nm)DFS

任意解的就是在上面Tarjan的基础上拓扑排序一下，每次选一个出度为0的未染色点，把它的对应点i和i的所有前驱全部标为不选。因为有之前那个性质所以并不用拓扑排序过程中无需判无解。