https://www.lydsy.com/JudgeOnline/problem.php?id=1997
https://www.luogu.org/problemnew/show/P3209
若能将无向图G=(V,E)画在平面上使得任意两条无重合顶点的边不相交，则称G是平面图。判定一个图是否为平面图的问题是图论中的一个重要问题。现在假设你要判定的是一类特殊的图，图中存在一个包含所有顶点的环，即存在哈密顿回路。
m>3*n+6显然为NO。
有一个想法就是把哈密顿回路当成一个壳，枚举每一条边，再枚举另一条边，很容易通过哈密顿序来判断两边是否相交。
那么此时相交是否输出NO呢？并不是。
（我纠结在这里，后来发现我游戏都白玩了，有一个解绳子的游戏，思考一下就知道可以把壳内的边移到壳外就可以解决矛盾。）
于是分成了两个区域：壳内和壳外。用并查集维护一下就行了。
#include<algorithm> #include<iostream> #include<cstring> #include<cctype> #include<cstdio> #include<vector> #include<cmath> using namespace std; const int N=210; const int M=10010; inline int read(){ int X=0,w=0;char ch=0; while(!isdigit(ch)){w|=ch=='-';ch=getchar();} while(isdigit(ch))X=(X<<3)+(X<<1)+(ch^48),ch=getchar(); return w?-X:X; } struct node{ int u,v; }e[M]; int n,m,pos[N],t[N],fa[M*2]; int find(int x){ if(fa[x]==x)return x; return fa[x]=find(fa[x]); } inline bool unionn(int x,int y){ int x1,y1; if(find(x)==find(y))return 0; x1=find(x),y1=find(y+m); if(x1!=y1)fa[x1]=y1; x1=find(x+m),y1=find(y); if(x1!=y1)fa[x1]=y1; return 1; } inline bool pan(int i,int j){ int xi=pos[e[i].u],yi=pos[e[i].v]; int xj=pos[e[j].u],yj=pos[e[j].v]; if(xi>yi)swap(xi,yi); if(xj>yj)swap(xj,yj); if(xi>xj)swap(xi,xj),swap(yi,yj); return xi<xj&&xj<yi&&yi<yj; } int main(){ int T=read(); while(T--){ bool ok=1; n=read(),m=read(); for(int i=1;i<=m;i++){ e[i].u=read(),e[i].v=read(); } for(int i=1;i<=n;i++)t[i]=read(),pos[t[i]]=i; if(m>3*n+6){puts("NO");continue;} for(int i=1;i<=2*m;i++)fa[i]=i; for(int i=1;i<=m&&ok;i++){ for(int j=i+1;j<=m&&ok;j++){ if(pan(i,j)){ ok=unionn(i,j); } } } if(!ok)puts("NO"); else puts("YES"); } return 0; }
+++++++++++++++++++++++++++++++++++++++++++
+本文作者：luyouqi233。 +
+欢迎访问我的博客：http://www.cnblogs.com/luyouqi233/ +
+++++++++++++++++++++++++++++++++++++++++++