链接：
题意：
给出 \(T\) 张无向图 \((T\leq100)\)，并给出它对应的哈密顿回路，判断每张图是否是平面图。
分析：
平面图判定问题貌似是有线性做法的，这里给出链接，不是本题解重点。
在想不到上述算法的情况下，我们发现题目给出了该图的哈密顿回路，所以我们把无向图按哈密顿回路排成一个环。此时不在环上的边之间才可能出现交叉，所以我们考虑暴力 \(O(m^2)\) 枚举，对于可能产生交叉的两条边，只有他们在环的两侧时才不会相交，所以当 \(a,b\) 两条边可能相交时， \(a\) 在内侧则 \(b\) 一定在外侧。发现了 2-sat 模型。
算法：
简单说下算法，先找到所有不在环上的边。\(O(m^2)\) 暴力枚举，判断每两条边是否可能相交，如果可能相交，那么在 2-sat 中
insert(i,j+tot);
insert(i+tot,j);
insert(j,i+tot);
insert(j+tot,i);
最后 tarjan 求强连通分量，\(O(m+m^2)\)。
总复杂度 \(O(m^2)\)。
优化：
显然 \(O(m^2)\) 的复杂度无法通过 \(M\leq10000\) 的数据，但学过平面图的我们发现可以利用平面图的性质将 \(m\) 优化至 \(n\) 的范围。
有
设G是一个面数为 f 的(n,m)连通简单平面图且n≥3,则m≤3n-6
我们可以特判 \(m\) 将 \(m\) 缩小到 \(3n-6\) 范围内，那么 \(O(n^2)\) 的时间复杂度就可以随便过了。
代码：
#include<bits/stdc++.h>
using namespace std;
#define in read()
inline int read(){
int p=0,f=1;
char c=getchar();
while(c>'9'||c<'0'){if(c=='-')f=-1;c=getchar();}
while(c>='0'&&c<='9'){p=p*10+c-'0';c=getchar();}
return p*f;
}
const int N=1205;
const int M=360005;
int ed[N],tot;
struct edge{
int v,next;
}e[M];
int head[N],en;
void insert(int u,int v){
e[++en].v=v;
e[en].next=head[u];
head[u]=en;
}
int n,m;
int sta[N],low[N],dfn[N],id[N],sum,sign,top;
bool vis[N];
void dfs(int u){
low[u]=dfn[u]=++sign;
vis[u]=true;sta[++top]=u;
for(int i=head[u];i;i=e[i].next){
int v=e[i].v;
if(!dfn[v]) dfs(v),low[u]=min(low[u],low[v]);
else if(vis[v]) low[u]=min(low[u],dfn[v]);
}
if(low[u]==dfn[u]){
sum++;int i=sta[top--];
while(i!=u){
vis[i]=false;
id[i]=sum;
i=sta[top--];
}
vis[i]=false;
id[i]=sum;
}
}
int q[205];
int p[205];
bool check(){
for(int i=1;i<=tot;i++)
if(id[i]==id[i+tot])
return false;
return true;
}
struct QWQ{
int a,b;
}a[10005];
void clean(){
memset(head,0,sizeof(head));
memset(dfn,0,sizeof(dfn));
memset(low,0,sizeof(low));
memset(sta,0,sizeof(sta));
memset(id,0,sizeof(id));
sum=sign=en=tot=top=0;
}
inline int cinab(int a,int b,int c){
return (c>a&&c<b)?1:0;
}
signed main(){
int T=in;
while(T--){
clean();
n=in,m=in;
for(int i=1;i<=m;i++)
a[i].a=in,a[i].b=in;
for(int i=1;i<=n;i++){
q[i]=in;
p[q[i]]=i;
//p[i] 是 i 在环上的次序
}
if(m>3*n-6){
cout<<"NO"<<'\n';
continue;
}
for(int i=1;i<=m;i++){
a[i].a=p[a[i].a],a[i].b=p[a[i].b];
if(a[i].a>a[i].b)
swap(a[i].a,a[i].b);
if(a[i].b-a[i].a!=1&&a[i].b-a[i].a!=n-1)
ed[++tot]=i;
}
for(int i=1;i<tot;i++)
for(int j=i+1;j<=tot;j++){
int xa=a[ed[i]].a,xb=a[ed[i]].b,ya=a[ed[j]].a,yb=a[ed[j]].b;
//我们用一个端点在第一条线内而另一个端点不在来判断，需要特判端点相同的情况
if(xa==ya||xa==yb||xb==ya||xb==yb)continue;
if(cinab(xa,xb,ya)^cinab(xa,xb,yb)){
insert(i,j+tot);
insert(i+tot,j);
insert(j,i+tot);
insert(j+tot,i);
}
}
for(int i=1;i<=tot*2;i++)if(!dfn[i])dfs(i);
if(check())cout<<"YES"<<'\n';
else cout<<"NO"<<'\n';
}
return 0;
}