Luogu3209 平面图判定

题面

简化题意

给定一个无向图，保证存在一条哈密顿回路。判定是否是平面图。

$3\leq n\leq 200,m\leq 10^4$。

题解

存在一条哈密顿回路，把这个回路当成一个圆，其他的边当成弦：

圆内弦相交显然不代表其不是平面图，可以把一些边拉在外面。这里可以把 $AD,AE$ 拉到圆外侧。

如果把所有有交点的弦提出来，则这两个弦不能都在圆内或圆外。这里存在一种 2SAT 的关系。转化成 2-SAT 问题的解的存在性判定即可。

题目的边数很大，不能枚举每条边。考虑平面图的性质：当 $n\geq 3$ 时有 $m\leq 3n-6$。提前判掉之后，$m$ 就是 $594$ 以内了。可以枚举两个相交的弦，然后跑 2-SAT 即可。

代码

#include<bits/stdc++.h>
using namespace std;
const int max_n=20005,max_m=2000006;
inline int read(){
    int x=0;bool w=0;char c=getchar();
    while(c<'0' || c>'9') w|=c=='-',c=getchar();
    while(c>='0' && c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();
    return w?-x:x;
}
struct graph{
    int ct,hd[max_n],to[max_m],nx[max_m];
    graph(){ct=1;}

    inline void clear(){
        ct=1;
        memset(hd,0,sizeof(hd));
    }
    inline void add(int u,int v){
        nx[++ct]=hd[u],hd[u]=ct,to[ct]=v;
    }
}e;

int n,m,a[max_n],b[max_n];

stack<int> s;
bool in[max_n];
int cntdfn,tot,dfn[max_n],low[max_n],col[max_n];

inline void Tarjan(int u,int fa){ // 2-SAT
    s.push(u),in[u]=1;
    dfn[u]=low[u]=++cntdfn;
    for(register int i=e.hd[u];i;i=e.nx[i]){
        int v=e.to[i];
        if(!dfn[v]){
            Tarjan(v,u);
            low[u]=min(low[u],low[v]);
        }
        else if(in[v])
            low[u]=min(low[u],dfn[v]);
    }
    if(dfn[u]==low[u]){
        int v=u;
        ++tot;
        do{
            v=s.top();s.pop();
            in[v]=0,
            col[v]=tot;
        }while(v!=u);
    }
}

struct edge{
    int u,v;
    edge(){u=v=0;}

    inline void init(int x,int y){
        u=x,v=y;
    }
}q[max_n];

#define opp(x) (x+m)
int cntid;
bool mp[max_n][max_n];

signed main(){
    int T=read();
    while(T--){
        n=read(),m=read();
        if(m>3*n-6){
            int x,y;
            for(register int i=1;i<=m;++i)
                x=read(),y=read();
            for(register int i=1;i<=n;++i)
                x=read();
            x+=y;
            puts("NO");
            continue;
        }
        cntdfn=cntid=tot=0;
        e.clear();
        while(!s.empty()) s.pop();
        memset(dfn,0,sizeof(dfn)),
        memset(low,0,sizeof(low)),
        memset(col,0,sizeof(col));

        for(register int i=1;i<=m;++i){
            int u=read(),v=read();
            mp[u][v]=mp[v][u]=1;
        }
        for(register int i=1;i<=n;++i){
            a[i]=read();
            b[a[i]]=i;
            if(i>=2)
                mp[a[i]][a[i-1]]=mp[a[i-1]][a[i]]=0;
            if(i==n)
                mp[a[1]][a[n]]=mp[a[n]][a[1]]=0;
        } // 过滤在圆上的边，得到弦
        for(register int i=2;i<=n;++i)
            for(register int j=1;j<i;++j)
                if(mp[i][j]){
                    q[++cntid].init(i,j);
                    mp[i][j]=mp[j][i]=0;
                }
                    
        m=cntid;
        for(register int i=2;i<=m;++i)
            for(register int j=1;j<i;++j){
                int u=b[q[i].u],v=b[q[i].v];
                int x=b[q[j].u],y=b[q[j].v];
                if(u>v) swap(u,v);
                if(x>y) swap(x,y);
                if((u<x && v>x && v<y) || (v>y && u>x && u<y)){
                    e.add(i,opp(j)),
                    e.add(opp(i),j),
                    e.add(j,opp(i)),
                    e.add(opp(j),i);
                }// 一个在外一个在内
            }
        for(register int i=1;i<=m*2;++i)
            if(!dfn[i])
                Tarjan(i,i);

        bool ok=1;
        for(register int i=1;i<=m && ok;++i)
            if(col[i]==col[opp(i)])
                ok=0;
        puts(ok?"YES":"NO");
    }
    return 0;
}