BZOJ1997 [Hnoi2010]Planar (2-sat)

题意：给你一个哈密顿图，判断是不是平面图

思路：先找出哈密顿图来。哈密顿回路可以看成一个环，把边集划分成两个集合，一个在环内，一个在外。如果有两条相交边在环内，则一定不是平面图，所以默认两条相交边，转化成2——sat，两条边不能同时在内或外，注意双向加边。（以边来转化成两倍）

 #include<cstdio>
 #include<cstring>
 #include<iostream>
 #include<queue>
 #include<stack>
 #include<bits/stdc++.h>
 using namespace std;
 #define LL long long
 #define clc(a,b) memset(a,b,sizeof(a))
 const int maxn =  + ;
 int r(){
     int x=,f=;char ch=getchar();
     while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}
     while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}
     return x*f;
 }
 int T,n,m,ind,top,cnt,scc;
 int u[],v[];
 int c[],pos[];
 int last[],dfn[],low[],q[],bl[];
 bool inq[]; struct edge{
     int to,next;
 }e[]; void add(int u,int v){
     e[++cnt].to=v;
     e[cnt].next=last[u];
     last[u]=cnt;
 } void tarjan(int x){
     inq[x]=;q[++top]=x;
     low[x]=dfn[x]=++ind;
     for(int i=last[x];i;i=e[i].next)
         if(!dfn[e[i].to])
             tarjan(e[i].to),low[x]=min(low[x],low[e[i].to]);
         else if(inq[e[i].to])
             low[x]=min(low[x],dfn[e[i].to]);
     int now=-;
     if(low[x]==dfn[x])
     {
         scc++;
         while(now!=x)
         {
             now=q[top--];inq[now]=;
             bl[now]=scc;
         }
     }
 } bool jude(){
     for(int i=;i<=m;i++){
         if(bl[i*]==bl[i*-])
             return false;
     }
  return true;
 }
 int main(){
     T=r();
     while(T--){
           n=r(),m=r();
           for(int i=;i<=m;i++){
             u[i]=r();v[i]=r();
           }
           clc(last,);
           cnt=;
           scc=ind=;
           clc(low,);
           clc(dfn,);
           for(int i=;i<=n;i++)
             c[i]=r();
         if(m>*n-){
             printf("NO\n");
             continue;
         }
         for(int i=;i<=n;i++)
             pos[c[i]]=i;
         top=;
         for(int i=;i<=m;i++){
             u[i]=pos[u[i]],v[i]=pos[v[i]];
             if(u[i]>v[i]) swap(u[i],v[i]);
             if(v[i]-u[i]==||v[i]-u[i]==n-) continue;
             u[++top]=u[i],v[top]=v[i];
         }
         m=top;
         for(int i=;i<=m;i++){
             for(int j=i+;j<=m;j++){
                 if((u[i]<u[j]&&v[i]>u[j]&&v[i]<v[j])||(u[i]>u[j]&&v[j]>u[i]&&v[i]>v[j])){
                     add(*i-,*j);
                     add(*i,*j-);
                     add(*j-,*i);
                     add(*j,*i-);
                 }
             }
         }
         for(int i=;i<=*m;i++){
            if(dfn[i]==){
             tarjan(i);
            }
         }
         if(jude()) printf("YES\n");
         else printf("NO\n");     }
     return ;
 }