P3209 [HNOI2010]平面图判定
斯德哥尔摩
2018-08-01 22:35:00
[P3209 [HNOI2010]平面图判定](https://www.luogu.org/problemnew/show/P3209)
看完题，蒟蒻表示边数怎么这么多？
然后看完题解，发现根据平面图的性质：边数小于等于$3n-6$。
不符合的直接跳过。
心里一句$MMP$。。。
然后可以发现，对于哈密尔顿环之外的任意一条边，要么连在环内部，要么连在环外部。
在一定的条件下（可以简单判断），如果两条边同时连在环内部或同时连在环外部，这两条边就一定会相交。
然后这种限制条件可以跑$2-SAT$。
把第$i$条**边**拆成$i$和$i'$，$i$表示这条边连在内部，$i'$表示连在外部。
对于任意两条不在哈密尔顿环上的边 $i->j,i\ !=j$，如果他们不能同时连在环内或环外，则：
1. 建边$i->j'$，表示$i$在内则$j$必须在外。
2. 建边$i'->j$，表示$i$在外则$j$必须在内。
3. 建边$j->i'$，表示$j$在内则$i$必须在外。
4. 建边$j'->i$，表示$j$在外则$i$必须在内。
然后$Tarjan$跑一遍强连通分量，如果存在一个$i$和$i'$在同一个强连通分量里，那么原图不是平面图，否则是平面图。
附代码：
```cpp
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#define MAXN 100010
#define MAXM 210
using namespace std;
int n,m,c,d,top,s,num;
int cstack[MAXN],head[MAXN],deep[MAXN],low[MAXN],colour[MAXN],path[MAXN],pos[MAXM];
bool vis[MAXN],circle[MAXM][MAXM];
struct Graph{
int next,to;
}a[MAXN<<1];
struct Edge{
int x,y;
}b[MAXN],g[MAXN];
inline int read(){
int date=0,w=1;char c=0;
while(c<'0'||c>'9'){if(c=='-')w=-1;c=getchar();}
while(c>='0'&&c<='9'){date=date*10+c-'0';c=getchar();}
return date*w;
}
inline void add(int x,int y){
a[c].to=y;a[c].next=head[x];head[x]=c++;
a[c].to=x;a[c].next=head[y];head[y]=c++;
}
void dfs(int x){
deep[x]=low[x]=d++;
vis[x]=true;
cstack[top++]=x;
for(int i=head[x];i;i=a[i].next){
int v=a[i].to;
if(!deep[v]){
dfs(v);
low[x]=min(low[x],low[v]);
}
else if(vis[v])low[x]=min(low[x],deep[v]);
}
if(low[x]>=deep[x]){
s++;
do{
colour[cstack[top-1]]=s;
vis[cstack[top-1]]=false;
}while(cstack[--top]!=x);
}
}
void work(){
if(m>3*n-6){
printf("NO\n");
return;
}
circle[path[n]][path[1]]=circle[path[1]][path[n]]=true;
pos[path[n]]=n;
for(int i=1;i<n;i++){
pos[path[i]]=i;
circle[path[i]][path[i+1]]=circle[path[i+1]][path[i]]=true;
}
for(int i=1;i<=m;i++){
if(circle[b[i].x][b[i].y])continue;
num++;
g[num].x=b[i].x;g[num].y=b[i].y;
}
m=num;
for(int i=1;i<=m;i++)
for(int j=i+1;j<=m;j++){
int x_one=pos[g[i].x],y_one=pos[g[i].y],x_two=pos[g[j].x],y_two=pos[g[j].y];
if(x_one>y_one)swap(x_one,y_one);
if(x_two>y_two)swap(x_two,y_two);
if((x_one<x_two&&x_two<y_one&&y_one<y_two)||(x_two<x_one&&x_one<y_two&&y_two<y_one)){
add(i,j+m);
add(i+m,j);
}
}
for(int i=1;i<=(m<<1);i++)if(!deep[i])dfs(i);
bool flag=true;
for(int i=1;i<=m&&flag;i++)if(colour[i]==colour[i+m])flag=false;
if(flag)printf("YES\n");
else printf("NO\n");
}
void init(){
c=d=top=1;
s=num=0;
memset(head,0,sizeof(head));
memset(deep,0,sizeof(deep));
memset(low,0,sizeof(low));
memset(colour,0,sizeof(colour));
memset(circle,false,sizeof(circle));
n=read();m=read();
for(int i=1;i<=m;i++){b[i].x=read();b[i].y=read();}
for(int i=1;i<=n;i++)path[i]=read();
}
int main(){
int t=read();
while(t--){
init();
work();
}
return 0;
}
```