[POJ3207]Ikki's Story IV - Panda's Trick（2-SAT）

题目大意：
圆上顺序排列n个点，现要在一些点间连边，边只能在圆内或圆外，求有没有可能不相交

学习了2-SAT！
参考资料如下：
1、神犇写的巨无敌详细的博客
2、我觉得很好看的懂的论文

好的那么我来捋一捋2-SAT的思路，首先对于一个选择进行拆点分成选和不选，对于约束关系，如果选了a不能选b的话，那就a向b的对称点连边。建图之后强联通缩点，如果有一对对称点在同一个连通分量那就说明无解。如果需要输出解那就进行拓扑排序之后染色，可以理解为走一遍进行选择。

对于这道题，我们通过画图可以发现：如果两条线在圆内有交点，那么他们在圆外也一定有交点。

所以我们只需要判断在两条边在圆内是否有交点代入2-SAT模型求解（通过端点判断即可）

#include<iostream>
#include<cstring>
using namespace std;
const int N=2010;
const int M=600010;
struct OrzAKC
{int x,y;
} a[M];
struct AKCqhzdy
{int x,y,next;
} b[M];
int n,m,len,top,idx,cnt;
int last[N],dfn[N],low[N],belong[N],sta[N];
bool instack[N];
void ins(int x,int y)
{b[len].x=x;b[len].y=y;b[len].next=last[x];last[x]=len++;
}
void tarjan(int x)
{int u;dfn[x]=low[x]=++idx;instack[x]=true;sta[++top]=x;for (int i=last[x]; i!=-1; i=b[i].next){int y=b[i].y;if (!dfn[y]) {tarjan(y);if (low[x]>low[y])low[x]=low[y];} else if (instack[y]&&low[x]>dfn[y])low[x]=dfn[y];}if(low[x]==dfn[x]){cnt++;do {u=sta[top--];instack[u]=false;belong[u]=cnt;} while (x!=u);}
}
void getmap()
{int i,j;memset(last,-1,sizeof(last));memset(dfn,0,sizeof(dfn));memset(low,0,sizeof(low));memset(belong,-1,sizeof(belong));memset(instack,false,sizeof(instack));len=0;top=0;cnt=top=idx=0;for (i=0; i<m; i++){scanf("%d%d",&a[i].x,&a[i].y);if(a[i].x>a[i].y){int t=a[i].x;a[i].x=a[i].y;a[i].y=t;}}for (i=0;i<m-1;i++)for (j=i+1;j<m;j++)if (a[i].x>a[j].x&&a[i].y>a[j].y&&a[j].y>a[i].x||a[i].x<a[j].x&&a[i].y<a[j].y&&a[i].y>a[j].x){ins(2*i,2*j+1);ins(2*j+1,2*i);ins(2*j,2*i+1);ins(2*i+1,2*j);}}
bool solve()
{for (int i=0;i<2*m;i++)if(!dfn[i])tarjan(i);for (int i=0;i<m;i++)if(belong[2*i]==belong[2*i+1])return false;return true;
}
int main()
{while (scanf("%d%d",&n,&m)!=EOF){getmap();if (solve()) printf("panda is telling the truth...\n");else printf("the evil panda is lying again\n");}
}