题目链接：戳我
我怎么知道平面图有这个性质？？
对于一个平面图，它的边数不超过点数的\(3n-6\)
所以可以直接把边数多的特判掉，剩下的图中边数和点数就是一个数量级的了。
因为这个图存在欧拉回路，所以我们先把那些构成欧拉回路的边拉出来，将边上的两个端点的标号替换成在这个序列上的位置。然后判断这些边能不能不相交。
对于两条边\(i,j\)（分别对应\((u1,v1),(u2,v2)\)），如果\(u1<u2<v1<v2\)——
那么这两个边肯定相交，不是平面图！！
那么这两个边肯定一个在环的内部，一个在外部。这种只有两种状态进行规划，判断有没有合法方案的题——显然能想到2-SAT。
我们连四条边，分别表示：
- i在内部那么j一定在外部
- i在外部那么j一定在内部
- j在内部那么i一定在外部
- j在外部那么i一定在内部
然后tarjan判断一下有没有同一条边的两个状态在一个SCC里即可。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#define MAXN 100010
using namespace std;
int n,m,t,tot,cnt,kkk,top,T;
int a[MAXN],b[MAXN],head[MAXN],pos[MAXN];
int dfn[MAXN],low[MAXN],in[MAXN],st[MAXN],c[MAXN];
struct Edge{int nxt,to,dis;}edge[MAXN<<1];
struct Line{int u,v;}line[MAXN<<1];
inline void add(int from,int to)
{
// printf("[%d %d]\n",from,to);
edge[++t].nxt=head[from],edge[t].to=to,head[from]=t;
}
inline void tarjan(int x)
{
dfn[x]=low[x]=++tot;
st[++top]=x;
in[x]=1;
for(int i=head[x];i;i=edge[i].nxt)
{
int v=edge[i].to;
if(!dfn[v]) tarjan(v),low[x]=min(low[x],low[v]);
else if(in[v]) low[x]=min(low[x],dfn[v]);
}
if(dfn[x]==low[x])
{
int v;
cnt++;
do{v=st[top--],in[v]=0,c[v]=cnt;}while(x!=v);
}
}
inline bool check()
{
for(int i=1;i<=m;i++)
if(c[i]==c[i+m])
return false;
return true;
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("ce.in","r",stdin);
#endif
scanf("%d",&T);
while(T--)
{
memset(head,0,sizeof(head));
memset(dfn,0,sizeof(dfn));
memset(low,0,sizeof(low));
memset(in,0,sizeof(in));
tot=top=cnt=t=kkk=0;
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++) scanf("%d%d",&line[i].u,&line[i].v);
for(int i=1;i<=n;i++)
{
int x;
scanf("%d",&x);
pos[x]=i;
}
for(int i=1;i<=m;i++) line[i].u=pos[line[i].u],line[i].v=pos[line[i].v];
if(m>3*n-6)
{
printf("NO\n");
continue;
}
for(int i=1;i<=m;i++)
if(abs(line[i].u-line[i].v)!=1)
{
line[++kkk]=line[i];
if(line[kkk].u>line[kkk].v) swap(line[kkk].u,line[kkk].v);
}
m=kkk;
for(int i=1;i<=m;i++)
for(int j=1;j<=m;j++)
if(line[i].u<line[j].u&&line[j].u<line[i].v&&line[j].v>line[i].v)
add(i+m,j),add(i,j+m),add(j,i+m),add(j+m,i);
for(int i=1;i<=2*m;i++)
if(!dfn[i])
tarjan(i);
// for(int i=1;i<=m;i++)
// printf("%d %d\n",c[i],c[i+m]);
if(check()==true) printf("YES\n");
else printf("NO\n");
}
return 0;
}