首页 > 代码库 > POJ 3207 Ikki's Story IV - Panda's Trick

POJ 3207 Ikki's Story IV - Panda's Trick

2-SAT判可行。

#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#define maxv 1050#define maxe 200500using namespace std;int n,m,a[maxv],b[maxv],g[maxv],nume=0,bel[maxv],dfn[maxv],low[maxv],times=0,cnt=0;int stack[maxv],top=0;bool vis[maxv];struct edge{    int v,nxt;}e[maxe];void addedge(int u,int v){    e[++nume].v=v;    e[nume].nxt=g[u];    g[u]=nume;}bool judge(int x,int y){    if ((a[x]<a[y]) && (a[y]<b[x]) && (b[x]<b[y])) return false;    if ((a[y]<a[x]) && (a[x]<b[y]) && (b[y]<b[x])) return false;    return true;}void tarjan(int x){    dfn[x]=low[x]=++times;stack[++top]=x;vis[x]=true;    for (int i=g[x];i;i=e[i].nxt)    {        int v=e[i].v;        if (!dfn[v])        {            tarjan(v);            low[x]=min(low[x],low[v]);        }        else if (vis[v]) low[x]=min(low[x],dfn[v]);    }    if (low[x]==dfn[x])    {        cnt++;        int now=0;        while (now!=x)        {            now=stack[top];top--;            bel[now]=cnt;vis[now]=false;        }    }}void get_ans(){    for (int i=1;i<=m;i++)    {        if (bel[i*2-1]==bel[i*2])        {            printf("the evil panda is lying again\n");            return;        }    }    printf("panda is telling the truth...\n");}int main(){    scanf("%d%d",&n,&m);    for (int i=1;i<=m;i++)    {        scanf("%d%d",&a[i],&b[i]);        if (a[i]>b[i]) swap(a[i],b[i]);    }    for (int i=1;i<=m;i++)        for (int j=i+1;j<=m;j++)        {            if (!judge(i,j))            {                addedge(i*2-1,j*2);addedge(j*2,i*2-1);                addedge(j*2-1,i*2);addedge(i*2,j*2-1);            }        }    for (int i=1;i<=2*m;i++)        if (!dfn[i]) tarjan(i);    get_ans();    return 0;}

 

POJ 3207 Ikki's Story IV - Panda's Trick