[HNOI2010] 平面图判定-平面图性质、带权并查集/2-sat
https://www.luogu.com.cn/problem/P3209
题意：给一张 \(n\) 个点，\(m\) 条边的哈密顿图，并且哈密顿回路已知，问是否是平面图，\(T\) 组询问。
\(1\leq T\leq 100,1\leq n\leq 200,1\leq m\leq 10^4\)。
转换挺奇妙的。
极大平面图
《离散数学》这课的高光时刻来了，没想到结课之后居然还会翻课件…
首先欧拉示性数公式告诉我们，一张简单的连通的平面图，点数 \(n\)，边数 \(m\) 和面数 \(f\) 有关系 \(n-m+f=2\)。
如果连通分支的个数变成 \(k\) 个，则不难发现，修正后的结果是
\[n-m+f=k+1 \]定理1.设 \(G\) 是连通的平面图，\(deg(R_i)\geq l\geq 3\)，则 \(m\leq \frac{l}{l-2}(n-2)\)，其中 \(R_i\) 表示平面图中的平面，\(deg(R_i)\) 则表示 \(R_i\) 这个平面的边数。
证：有类似于握手定理的 \(2m=\sum deg(R_i)\geq l\times f\geq l(2-n+m)\)，即有
\[2m\geq ml+l(2-n) \]化简得到 \((2-l)m\geq l(2-n)\)，因为 \(l\geq 3\)，所以 \(m\leq \frac{l}{l-2}(n-2)\).
定理2. 设 \(G\) 是简单平面图，且\(n\geq 3\) 则 \(m\leq 3n-6\)。
证：假设有 \(k\) 个连通分支，如果 \(G\) 是森林，则 \(m\leq n-1\leq 3n-6\)（当 \(n\geq 3\) ），否则 \(G\) 的某个连通分支有环，而简单图的环至少是三元环，因此这个子图有 \(m\leq \frac{3}{1}(n-k-1)=3(n-2)\).
并查集
所以这题虽然 \(m\) 取到了 \(10^4\) ，但其实只有 \(m\leq 3n-6<300\) 才需要判断。
-
而对于 \(m\) 小的情况，因为哈密顿回路已经给出了，所以先把点按照其在哈密顿回路上的顺序排好。
-
再考虑任意两条边，如果位置存在交叉的情况，那么一定是一个在内侧，一个在外侧的，就转化成了一个 2-sat 的模型。
-
但仔细一想，这个排斥关系是相互的（即如果我们考虑2-sat的建图，就会变成：如果 \(i\to j\) 有边，那么 \(j\to i\) 也有边），所以其实是个无向图
-
所以直接用带权并查集就行了。
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define endl '\n'
#define fastio ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
using namespace std;
const int N=205;
namespace DSU{
int fa[N*3],dep[N*3],bad;
int find(int x){
if(fa[x]==x)return x;
int t=dep[fa[x]]; //这里注意一下要先把压缩前的距离存下来
fa[x]=find(fa[x]);
dep[x]^=t;
return fa[x];
}
void init(int n){
bad=0;
rep(i,0,n-1)fa[i]=i,dep[i]=0;
}
void merge(int x,int y){
int fx=find(x),fy=find(y);
if(fx==fy){
if(dep[x]==dep[y])bad=1;
return ;
}
fa[fy]=fx;
dep[fy]=(dep[x]^dep[y]^1);
}
};
int n,m,v[N],pos[N];
vector<pair<int,int>> E;
int main(){
fastio;
int tc;cin>>tc;
while(tc--){
cin>>n>>m;
E.resize(m);
rep(i,0,m-1)cin>>E[i].first>>E[i].second;
m=E.size();
rep(i,1,n)cin>>v[i];
if(m>3*n-6)cout<<"NO"<<endl;
else{
rep(i,1,n)pos[v[i]]=i;
rep(i,0,m-1){
E[i].first=pos[E[i].first];
E[i].second=pos[E[i].second];
if(E[i].first>E[i].second)swap(E[i].first,E[i].second);
}
DSU::init(m);
rep(i,0,m-1){
int l=E[i].first,r=E[i].second;
rep(j,i+1,m-1){
int p=E[j].first,q=E[j].second;
if((l<p&&p<r&&r<q)||(p<l&&l<q&&q<r))DSU::merge(i,j);//两种都要判
}
}
if(DSU::bad)cout<<"NO"<<endl;
else cout<<"YES"<<endl;
}
}
return 0;
}