P3209 [HNOI2010]平面图判定

P3209 [HNOI2010]平面图判定

哈密尔顿环之外的任意一条边，要么连在环内部，要么连在环外部

判断两条边在同一部分会相交，则这两条边必须分开

那么把边看作点连边，跑二分图染色就行

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<iostream>

using namespace std;

typedef long long LL;

const LL maxn=500000;

inline LL read(){

    LL x=0,f=1; char c=getchar();

    while(c<'0'||c>'9'){

        if(c=='-') f=-1; c=getchar();

    }

    while(c>='0'&&c<='9'){

        x=x*10+c-'0'; c=getchar();

    }return x*f;

}

struct node{

    LL to,next;

}dis[maxn];

LL T,num,n,m;

LL head[maxn],belong[maxn],edge[maxn][2],a[maxn];

bool f;

inline void Add(LL u,LL v){

    dis[++num]=(node){v,head[u]}; head[u]=num;

}

inline bool Check(LL u1,LL v1,LL u2,LL v2){

    return (u1<u2&&u2<v1&&v1<v2)||(u2<u1&&u1<v2&&v2<v1);

}

bool Dfs(LL u,LL c){

    belong[u]=c;

    for(LL i=head[u];i;i=dis[i].next){

        LL v=dis[i].to;

        if(belong[v]==c)

            return false;

        if(!belong[v]&&!Dfs(v,3-c))

            return false;

    }

    return true;

}

int main(){

    T=read();

    while(T--){

        n=read(),m=read();

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

            edge[i][0]=read(),

            edge[i][1]=read();

        for(LL i=1;i<=n;++i)

            a[read()]=i;

        if(m>3*n-6){

            printf("NO\n");

            continue;

        }

        memset(head,0,sizeof(head)); num=0;

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

            for(LL j=i+1;j<=m;++j){

            	LL u1=a[edge[i][0]],v1=a[edge[i][1]];

            	LL u2=a[edge[j][0]],v2=a[edge[j][1]];

            	if(u1>v1)

            	    swap(u1,v1);

            	if(u2>v2)

            	    swap(u2,v2);

            	if(Check(u1,v1,u2,v2)){

            		Add(i,j);

            		Add(j,i);

                }

            }

        f=false;

        memset(belong,0,sizeof(belong));

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

            if(!belong[i])

            	if(!Dfs(i,1)){

            		f=true;

            		break;

                }

        if(f)

            printf("NO\n");

        else

            printf("YES\n");

    }

    return 0;

}