若能将无向图G=(V,E)画在平面上使得任意两条无重合顶点的边不相交，则称G是平面图。判定一个图是否为平面图的问题是图论中的一个重要问题。现在假设你要判定的是一类特殊的图，图中存在一个包含所有顶点的环，即存在哈密顿回路。

m>3*n+6显然为NO。

有一个想法就是把哈密顿回路当成一个壳，枚举每一条边，再枚举另一条边，很容易通过哈密顿序来判断两边是否相交。

那么此时相交是否输出NO呢？并不是。

（我纠结在这里，后来发现我游戏都白玩了，有一个解绳子的游戏，思考一下就知道可以把壳内的边移到壳外就可以解决矛盾。）

于是分成了两个区域：壳内和壳外。用并查集维护一下就行了。

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            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
            
             
              
               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。 　　　　　　　　　　　　　　+

+欢迎访问我的博客： +

+++++++++++++++++++++++++++++++++++++++++++