题意:若能将无向图 (G=(V, E)) 画在平面上使得任意两条无重合顶点的边不相交，则称 (G) 是平面图。判定一个图是否为平面图的问题是图论中的一个重要问题。现在假设你要判定的是一类特殊的图，图中存在一个包含所有顶点的环，即存在哈密顿回路。(n<=200,m<=10000.)
分析:寻思了半天,题目中的平面图应该就是我们画的那种平面图,然后每条边不能相交这种吧.
首先根据平面图性质特判(不要问我怎么知道的):(m>3*n-6),就一定不会是平面图,那么边数直接从(10000)级别下降到了(600)级别(就可以暴力做了???).
然后题目中给了我们一个环,不妨设这个环的节点编号就是(1->2->3->...->n),那么对于剩下的非环上的边,它们的边要么在环外要么在环内,就可以把每条边拆成两个,一个表示在环内,一个表示在环外,然后根据(2-SAT)连边跑(tarjan)判定即可.
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
#include<map>
#include<set>
#define ll long long
using namespace std;
inline int read(){
int x=0,o=1;char ch=getchar();
while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar();
if(ch=='-')o=-1,ch=getchar();
while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
return x*o;
}
const int N=605;
const int M=100005;//这个数组我也不知道要开多大
struct edge{int x,y;}E[M],e[M];
int tot,head[N],nxt[M],to[M],a[N];
inline void add(int a,int b){nxt[++tot]=head[a];head[a]=tot;to[tot]=b;}
int top,tim,num,dfn[N],low[N],st[N],color[N];
inline void tarjan(int u){
dfn[u]=low[u]=++tim;st[++top]=u;
for(int i=head[u];i;i=nxt[i]){
int v=to[i];
if(!dfn[v]){
tarjan(v);
low[u]=min(low[u],low[v]);
}
else if(!color[v]){
low[u]=min(low[u],dfn[v]);
}
}
if(low[u]==dfn[u]){
color[u]=++num;
while(st[top]!=u){
color[st[top]]=num;
--top;
}
--top;
}
}
int main(){
int T=read();
while(T--){
int n=read(),m=read();
tot=0;tim=0;top=0;num=0;
memset(dfn,0,sizeof(dfn));
memset(head,0,sizeof(head));
memset(color,0,sizeof(color));//多组数据初始化
for(int i=1;i<=m;++i)E[i].x=read(),E[i].y=read();
for(int i=1;i<=n;++i)a[read()]=i;//把节点重新编号
if(m>3*n-6){puts("NO");continue;}//特判
int cnt=0;
for(int i=1;i<=m;++i){
E[i].x=a[E[i].x],E[i].y=a[E[i].y];//赋予新的编号
if(E[i].x>E[i].y)swap(E[i].x,E[i].y);
if(E[i].x+1!=E[i].y&&!(E[i].x==1&&E[i].y==n))e[++cnt].x=E[i].x,e[cnt].y=E[i].y;//非环上的边就保留下来
}
for(int i=1;i<=cnt;++i)
for(int j=1;j<=cnt;++j)
if(e[i].x<e[j].x&&e[j].x<e[i].y&&e[i].y<e[j].y)
//只有节点编号相交叉的两条边才可能相交,这种边就需要讨论在环外还是环内
add(i,j+cnt),add(j,i+cnt),add(i+cnt,j),add(j+cnt,i);
for(int i=1;i<=cnt*2;++i)if(!dfn[i])tarjan(i);
int bj=1;
for(int i=1;i<=cnt;++i)if(color[i]==color[i+cnt]){bj=0;break;}
if(bj)puts("YES");else puts("NO");
}
return 0;
}