include <iostream>

using namespace std;

const int mymax1=500;
int root[mymax1];//等于自己的是根
bool relation[mymax1];//true是必须相同，false是必须相反

int bcj_root(int x);
bool bcj_union(int x,int y);


int main()
{
    int a[mymax1],b[mymax1];
    int n,m,i,j,temp;
    bool truth;
    cin>>n>>m;
    for(i=0;i<m;i++)
    {
        cin>>a[i]>>b[i];
        if(a[i]>=n || b[i]>=n)
        {
            cout<<"the evil panda is lying again"<<endl;
            return 0;
        }
        if(a[i]>b[i])
        {
            temp=a[i];
            a[i]=b[i];
            b[i]=temp;
        }
    }
    for(i=0;i<m;i++)
    {
        root[i]=i;
        relation[i]=true;
    }
    truth=true;
    for(i=0;i<m && truth;i++)
    {
        for(j=0;j<i && truth;j++)
        {
            if( (a[i]-a[j]) * (a[i]-b[j]) * (b[i]-a[j]) * (b[i]-b[j] ) == 0)
            {
                cout<<"the evil panda is lying again"<<endl;
                return 0;
            }
            else if( (a[i]<a[j]&&b[i]<b[j]&&a[j]<b[i]) || (a[j] < a[i]&&b[j] < b[i]&&a[i]<b[j]))
            {
                if( !bcj_union(i,j) )
                {
                    truth=false;
                }
            }
        }
    }
    if(truth) cout<<"panda is telling the truth..."<<endl;
    else cout<<"the evil panda is lying again"<<endl;
    return 0;
}


int bcj_root(int x)
{
    if(root[x]!=x)
    {
        int temproot=root[x];
        root[x]=bcj_root(root[x]);
        relation[x]=!(relation[x] ^ relation[temproot]);
    }
    return root[x];
}

bool bcj_union(int x,int y)
{
    if(bcj_root(x)==bcj_root(y) )
    {
        if( relation[x]==relation[y] ) return false;
        else return true;
    }
    //root[y]=bcj_root(y);
    relation[bcj_root(x)]=relation[x]^relation[y];
    root[bcj_root(x)]=bcj_root(y);
    return true;
}

• Re:我用并查集过的，发代码！ (2071) D0153 2009-08-16 08:56:42
• 求问思路是什么，写个简单的伪代码好吗，想学习下，这个看的太累。。 (0) agralol 2010-09-16 16:44:58
• 敬拜大牛，求照片膜拜 (2) dut200901102 2010-10-19 13:52:01
• 答楼上问，并查集的大致思路 (238) lexdene 2010-10-19 14:03:52
  • 这是2-sat的朴素实现吧。。。 (0) Snow_storm 2011-02-21 16:33:48