Problem

给定一个图，告诉你图的一条哈密顿回路，判定该图是否为一个平面图。

Solution

平面图的定义：一个图，放置在平面上，任意边皆不相交。这种图叫做平面图。
欧拉定理：设多个多边形的节点数，边数和分割的平面数分别为 $n,m,c$，相交的连同块的个数为 f，则 $n-m+c=f+1$。
对于一个极大平面图，由于一个面会使用一定三条边（即使是 4 条边，由于极大，也被分割成了 3 条边的面），而每条边一定被共用两次。所以有：$2c=3m$。
将两个算式合并，得到极大平面图 $3n-6=m$。则若 $m>3n-6$，该图不可能为平面图。

给出了哈密顿回路相当于给出了一个圈。
一条边可以从圈内一条直线连过去，也可以弯到圈外来连。
由于给出了哈密顿回路，只需判断两边若连圈内是否相交。如果相交，则这两条边要么一个圈内一个圈外。

可以转化成 2 -SAT 求解。
实际上也等价于二分图染色求解。

Code

// Code by ajcxsu
// Problem: planar

#include<bits/stdc++.h>
#define CLR(x) memset(x,0,sizeof(x))
#define DEBUG cout<<"Passing Line "<<__LINE__<<" in "<<__FUNCTION__<<"..."<<endl
using namespace std;

const int N=10000,M=1e5;

struct Edge {
    int u,v;
} e[N];

int ran[N];

int h[N],to[M],nexp[M],p=1;
inline void ins(int a, int b) { nexp[p]=h[a], h[a]=p, to[p]=b, p++; }

bool flag;
int col[N];
void paint(int x,int nc) {
    for(int u=h[x];u && !flag;u=nexp[u])
        if(!col[to[u]]) col[to[u]]=nc^1, paint(to[u], nc^1);
        else if(col[to[u]]==nc) flag=1;
}

void init() { CLR(h), p=1; flag=0; CLR(col); }
int main() {
    ios::sync_with_stdio(false);
    int T;
    cin>>T;
    int n,m;
    while(T--) {
        init();
        cin>>n>>m;
        for(int i=0;i<m;i++) cin>>e[i].u>>e[i].v;
        int na;
        for(int i=1;i<=n;i++) cin>>na, ran[na]=i;
        if(m>3*n-6) { cout<<"NO"<<endl; continue; }
        for(int i=0;i<m;i++) {
            e[i].u=ran[e[i].u], e[i].v=ran[e[i].v];
            if(e[i].u>e[i].v) swap(e[i].u, e[i].v);
        }
        Edge a,b;
        for(int i=0;i<m;i++)
                for(int j=i+1;j<m;j++) {
                    a=e[i], b=e[j];
                    if(a.u>b.u) swap(a,b);
                    if(b.u>a.u && b.u <a.v && a.v>b.u && a.v<b.v) ins(i,j), ins(j,i);
                }
        for(int i=0;i<m && !flag;i++)
            if(!col[i]) paint(i,2);
        if(flag) cout<<"NO"<<endl;
        else cout<<"YES"<<endl;
    }
    return 0;
}

本文链接：https://pst.iorinn.moe/archives/sol_luogu_p3209.html
许可： https://pst.iorinn.moe/license.html
若无特别说明，博客内的文章默认将采用 CC BY 4.0 许可协议 进行许可☆