学步园

题意理解有问题。      以为是是否存在相交直线了。   忽略了可以在圆外部连的情况。

自己有心理阴影了。    读题有心理阴影了肿么破。  呵~~~~~~~~~~

正解。  2-SAT一水。

我老是感觉这题与2-SAT不太相关。。

这题是必须同为真或同为假。   不像2-SAT的1为真或2为真。   并且里面连线之后外面照常可以连。  囧 ，难道又是破题意有误？ 

行了，直接题解吧，被题意坑坏了。

果然，考虑点是不满足2-SAT的条件，可是可以考虑边。。。囧了。。。。。。     是否是可析取或可以加条件。

AC了。。

思路过程：  1.直接暴力，题意理解是只能所有线段都在园内或圆外， WA

                      2.后来试了几次感觉好像题意理解有问题， 只看了题意，原来可以“曲”在圆外。

                      3.试了试2-SAT以点为判断  感觉与2-SAT相应条件不符  WA+++

                      4.参考了一下解题报告，可以枚举边的2-SAT思路，好像会了，顺便对2-SAT LRJ版稍微理解了点。

                      5.AC        别人的2-SAT模板（仅网上）一般都是用tarjan判断是否有i,i+1在同一个连通分量里面。 LRJ的代码其实也类似思路。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;
const int maxn=1005;
int n;
vector<int> G[maxn*2];
bool mark[maxn*2];
int s[maxn*2],c;
struct xx
{
    int be,en;
}x[5555];

bool dfs(int x)
{
    if(mark[x^1]) return false;
    if(mark[x]) return true;
    mark[x]=true;
    s[c++]=x;
    for(int i=0;i<G[x].size();i++)
        if(!dfs(G[x][i])) return false;
    return true;
}

void init()
{
    for(int i=0;i<n*2;i++)  G[i].clear();
    memset(mark,0,sizeof(mark));
}

void add(int x,int xval,int y,int yval)
{
    x=x*2+xval;
    y=y*2+yval;
    G[x^1].push_back(y);
    G[y^1].push_back(x);
}

bool solve()
{
    for(int i=0;i<n*2;i+=2)
        if(!mark[i]&&!mark[i+1])
        {
            c=0;
            if(!dfs(i))
            {
                while(c>0) mark[s[--c]]=false;
                if(!dfs(i+1)) return false;
            }
        }
    return true;
}

bool judge(int a,int b,int c,int d)
{
    if((a<c&&c<b&&b<d)||(c<a&&a<d&&d<b)) return true;
    else return false;
}

int main()
{
    int m,a,b;
    scanf("%d%d",&n,&m);
    init();
    for(int i=0;i<m;i++)
    {
        scanf("%d%d",&x[i].be,&x[i].en);
        if(x[i].be>x[i].en)
            swap(x[i].be,x[i].en);
    }
    for(int i=0;i<m;i++)
        for(int j=i+1;j<m;j++)
        {
            if(judge(x[i].be,x[i].en,x[j].be,x[j].en))
            {
                G[i*2].push_back(j*2+1);
                G[j*2].push_back(i*2+1);
                G[i*2+1].push_back(j*2);
                G[j*2+1].push_back(i*2);
            }
        }
    if(solve()==true) printf("panda is telling the truth...\n");
    else printf("the evil panda is lying again\n");
    return 0;
}