考虑题目中给了一个哈密顿回路，那么我们把这个哈密顿回路在草稿纸上画成一个环。。。
然后考虑还不在环上的边，这些边有两种加入的方法，一是画在环的里面，二是画在环的外面。。。
对于两个冲突的边，那么他们两个人必须选择不同的画法才能不相交。。。
那么这个东西可以用二分图判定或者2-SAT来实现。。。interesting。。。
然而这个题有一个数组没memset调了半天。。。(注意m>3*n-6时要直接判掉。。。这是一个结论。。。)
// MADE BY QT666
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<iostream>
#include<cstring>
using namespace std;
typedef long long ll;
const int N=200050;
struct data{
int x,y;
}e[N];
int T,n,m,rnk[N],c[N],bj[N];
int head[N],to[N],nxt[N],cnt,vis[N],flag,tmp,tmp2;
void lnk(int x,int y){
to[++cnt]=y,nxt[cnt]=head[x],head[x]=cnt;
to[++cnt]=x,nxt[cnt]=head[y],head[y]=cnt;
}
bool judge(int x1,int y1,int x2,int y2){
if(x1>y1) swap(x1,y1);
if(x2>y2) swap(x2,y2);
if((x1<x2&&y1>x2&&y1<y2)||(x2<x1&&y2>x1&&y2<y1)) return 1;
return 0;
}
void dfs(int x,int fa,int cor){
vis[x]=cor;
for(int i=head[x];i;i=nxt[i]){
int y=to[i];
if(y!=fa){
if(vis[y]==-1) dfs(y,x,cor^1);
else if(vis[y]!=(cor^1)) flag=1;
}
}
}
int main(){
scanf("%d",&T);
while(T--){
scanf("%d%d",&n,&m);flag=0;
memset(head,0,sizeof(head));cnt=0,tmp=0;tmp2=0;
memset(vis,-1,sizeof(vis));
memset(bj,0,sizeof(bj));
for(int i=1;i<=m;i++) scanf("%d%d",&e[i].x,&e[i].y);
for(int i=1;i<=n;i++) scanf("%d",&c[i]),rnk[c[i]]=i;
if(m>3*n-6) {puts("NO");continue;}
for(int i=1;i<=m;i++){
int x=rnk[e[i].x],y=rnk[e[i].y];
if(x>y) swap(x,y);
if(y-x==1||(y==n&&x==1)) bj[i]=1,tmp2++;
}
for(int i=1;i<=m;i++){
for(int j=i+1;j<=m;j++){
if(judge(rnk[e[i].x],rnk[e[i].y],rnk[e[j].x],rnk[e[j].y])&&bj[i]==0&&bj[j]==0){
lnk(i,j),tmp++;
}
}
}
for(int i=1;i<=m;i++) if(vis[i]==-1&&bj[i]==0) dfs(i,i,0);
if(flag) puts("NO");
else puts("YES");
}
return 0;
}
原文：http://www.cnblogs.com/qt666/p/7231453.html