传送门：Ikki's Story IV - Panda's Trick
题意：给定一个圆，圆上一些点。两点一线。现给出一些线，这些线可以在圆内连起来，也可以在圆外。问有没有可能所有的线画完且不出现相交。
分析：对于每条线，要么在圆外，要么在圆内，且不可同时满足，只能两者取一，判断这M条线是否合法，也就是M条线不冲突，这就是典型的2-sat问题了。
将每条线在圆内当成一点i，在圆外当成一点i'，对于两条线，如果在园内同时在圆内，那么必定也不能同时在园外，则有边(i, j') 、(j ,i')、(i'，j)、(j' ,i)。
这题由于不用输出方案，直接tarjan缩点后判断[i,i']是否属于一个强连通内即可。
#include <cstdio>
#include <cstring>
#include <string>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <queue>
#include <cstdlib>
#include <stack>
#include <vector>
#include <set>
#include <map>
#define LL long long
#define mod 100000000
#define inf 0x3f3f3f3f
#define eps 1e-6
#define N 2010
#define FILL(a,b) (memset(a,b,sizeof(a)))
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define PII pair<int,int>
using namespace std;
struct edge
{
int v,next;
edge(){}
edge(int v,int next):v(v),next(next){}
}e[N*N/];
struct node
{
int l,r;
}s[N];
int n,m,scc,step,top,tot;
int head[N],dfn[N],low[N],belong[N],Stack[N];
bool instack[N];
void init()
{
tot=;step=;scc=;top=;
FILL(head,-);FILL(dfn,);
FILL(low,);FILL(instack,false);
}
void addedge(int u,int v)
{
e[tot]=edge(v,head[u]);
head[u]=tot++;
}
void tarjan(int u)
{
int v;
dfn[u]=low[u]=++step;
Stack[top++]=u;
instack[u]=true;
for(int i=head[u];~i;i=e[i].next)
{
v=e[i].v;
if(!dfn[v])
{
tarjan(v);
low[u]=min(low[u],low[v]);
}
else if(instack[v])
{
low[u]=min(low[u],dfn[v]);
}
}
if(dfn[u]==low[u])
{
scc++;
do
{
v=Stack[--top];
instack[v]=false;
belong[v]=scc;
}while(v!=u);
}
}
bool ok(int i,int j)
{
int x1=s[i].l,y1=s[i].r;
int x2=s[j].l,y2=s[j].r;
if( x2>x1&&x2<y1 ){
if( y2>=y1 ) return true;
if( y2<=x1 ) return true;
}
if( y2>x1&&y2<y1 ){
if( x2>=y1 ) return true;
if( x2<=x1 ) return true;
}
return false;
}
void solve()
{
for(int i=;i<=*m;i++)
if(!dfn[i])tarjan(i);
bool flag=true;
for(int i=;i<=m;i++)
{
if(belong[i]==belong[i+m])
{
flag=false;
break;
}
}
if(flag)puts("panda is telling the truth...");
else puts("the evil panda is lying again");
}
int main()
{
int a,b;
while(scanf("%d%d",&n,&m)>)
{
init();
for(int i=;i<=m;i++)
{
scanf("%d%d",&a,&b);
a++;b++;
s[i].l=min(a,b);
s[i].r=max(a,b);
}
for(int i=;i<=m;i++)
for(int j=i+;j<=m;j++)
if(ok(i,j))
{
addedge(i,j+m);
addedge(j+m,i);
addedge(j,i+m);
addedge(i+m,j);
}
solve();
}
}