题目链接：

id=3207">http://poj.org/problem?

id=3207

4 2

0 1

3 2

panda is telling the truth...

[Submit]   [Go Back]   [Status]  
[

problem_id=3207" style="text-decoration:none">Discuss]

题目意思：

n个点。标号为0~n-1,顺序摆在一个圆盘的边缘上，如今给出m条边，每条边连接两个点。能够在圆盘里面或外面。推断这些边是否交叉。

解题思路：

2-SAT

把边抽象成点，假设内部连成的边抽象为i。则相应的边在外部则为i',推断随意两条边是否冲突。假设冲突的话。仅仅能一个放在外面。一个放在里面。

i和j冲突，则建图i'->j j->i' i->j' j'->i

代码：

//#include<CSpreadSheet.h>

#include<iostream>

#include<cmath>

#include<cstdio>

#include<sstream>

#include<cstdlib>

#include<string>

#include<string.h>

#include<cstring>

#include<algorithm>

#include<vector>

#include<map>

#include<set>

#include<stack>

#include<list>

#include<queue>

#include<ctime>

#include<bitset>

#include<cmath>

#define eps 1e-6

#define INF 0x3f3f3f3f

#define PI acos(-1.0)

#define ll __int64

#define LL long long

#define lson l,m,(rt<<1)

#define rson m+1,r,(rt<<1)|1

#define M 1000000007

//#pragma comment(linker, "/STACK:1024000000,1024000000")

using namespace std;

#define Maxn 1100

int n,m;

vector<vector<int> >myv;

int low[Maxn],dfn[Maxn],sta[Maxn],bc,sc,dep;

int in[Maxn];

bool iss[Maxn];

int x[Maxn],y[Maxn];

bool iscan(int a,int b)

{

    if(x[a]<x[b]&&(y[a]>x[b]&&y[a]<y[b]))

        return true;

    if(x[a]>x[b]&&x[a]<y[b]&&y[a]>y[b])

        return true;

    return false;

}

void tarjan(int cur)

{

    int ne;

    low[cur]=dfn[cur]=++dep;

    sta[++sc]=cur;

    iss[cur]=true;

    for(int i=0;i<myv[cur].size();i++)

    {

        ne=myv[cur][i];

        if(!dfn[ne])

        {

            tarjan(ne);

            low[cur]=min(low[cur],low[ne]);

        }

        else if(iss[ne]&&dfn[ne]<low[cur])

            low[cur]=dfn[ne];

    }

    if(low[cur]==dfn[cur])

    {

        ++bc;

        do

        {

            ne=sta[sc--];

            in[ne]=bc;

            iss[ne]=false;

        }while(ne!=cur);

    }

}

void solve()

{

    low[1]=dfn[1]=bc=sc=dep=0;

    memset(iss,false,sizeof(iss));

    memset(dfn,0,sizeof(dfn));

    for(int i=1;i<=2*m;i++)

        if(!dfn[i])

            tarjan(i);

}

int main()

{

    //freopen("in.txt","r",stdin);

   //freopen("out.txt","w",stdout);

   while(~scanf("%d%d",&n,&m))

   {

       for(int i=1;i<=m;i++)

       {

           scanf("%d%d",&x[i],&y[i]);

           if(x[i]>y[i])

                swap(x[i],y[i]);

       }

       myv.clear();

       myv.resize(m*2+10);

       for(int i=1;i<=m;i++)

       {

           for(int j=i+1;j<=m;j++)

           {

               if(iscan(i,j))

               {

                   myv[2*i].push_back(2*j-1);

                   myv[2*j-1].push_back(2*i);

                   myv[2*i-1].push_back(2*j);

                   myv[2*j].push_back(2*i-1);

               }

           }

       }

       solve();

       bool ans=true;

       for(int i=1;i<=m;i++)

       {

           if(in[2*i]==in[2*i-1])

           {

               ans=false;

               break;

           }

       }

       if(ans)

            printf("panda is telling the truth...\n");

       else

            printf("the evil panda is lying again\n");

   }

    return 0;

}