洛谷 P3209 [HNOI2010] 平面圖判定

連結：

P3209

題意：

給出 \(T\) 張無向圖 \((T\leq100)\)，并給出它對應的哈密頓回路，判斷每張圖是否是平面圖。

分析：

平面圖判定問題貌似是有線性做法的，這裡給對外連結接，不是本題解重點。

在想不到上述算法的情況下，我們發現題目給出了該圖的哈密頓回路，是以我們把無向圖按哈密頓回路排成一個環。此時不在環上的邊之間才可能出現交叉，是以我們考慮暴力 \(O(m^2)\) 枚舉，對于可能産生交叉的兩條邊，隻有他們在環的兩側時才不會相交，是以當 \(a,b\) 兩條邊可能相交時， \(a\) 在内側則 \(b\) 一定在外側。發現了 2-sat 模型。

算法：

簡單說下算法，先找到所有不在環上的邊。\(O(m^2)\) 暴力枚舉，判斷每兩條邊是否可能相交，如果可能相交，那麼在 2-sat 中

insert(i,j+tot);
				insert(i+tot,j);
				insert(j,i+tot);
				insert(j+tot,i);
           

最後 tarjan 求強連通分量，\(O(m+m^2)\)。

總複雜度 \(O(m^2)\)。

優化：

代碼：

#include<bits/stdc++.h>
using namespace std;
#define in read()
inline int read(){
	int p=0,f=1;
	char c=getchar();
	while(c>'9'||c<'0'){if(c=='-')f=-1;c=getchar();}
	while(c>='0'&&c<='9'){p=p*10+c-'0';c=getchar();}
	return p*f;
}
const int N=1205;
const int M=360005;
int ed[N],tot;
struct edge{
	int v,next;
}e[M];
int head[N],en;
void insert(int u,int v){
	e[++en].v=v;
	e[en].next=head[u];
	head[u]=en;
}
int n,m;
int sta[N],low[N],dfn[N],id[N],sum,sign,top;
bool vis[N];
void dfs(int u){
	low[u]=dfn[u]=++sign;
	vis[u]=true;sta[++top]=u;
	for(int i=head[u];i;i=e[i].next){
		int v=e[i].v;
		if(!dfn[v]) dfs(v),low[u]=min(low[u],low[v]);
		else if(vis[v]) low[u]=min(low[u],dfn[v]); 
	}
	if(low[u]==dfn[u]){
		sum++;int i=sta[top--];
		while(i!=u){
			vis[i]=false;
			id[i]=sum;
			i=sta[top--];
		}
		vis[i]=false;
		id[i]=sum;
	}
}
int q[205];
int p[205];
bool check(){
	for(int i=1;i<=tot;i++)
		if(id[i]==id[i+tot])
			return false;
	return true;
}
struct QWQ{
	int a,b;
}a[10005];
void clean(){
	memset(head,0,sizeof(head));
	memset(dfn,0,sizeof(dfn));
	memset(low,0,sizeof(low));
	memset(sta,0,sizeof(sta));
	memset(id,0,sizeof(id));
	sum=sign=en=tot=top=0;
}
inline int cinab(int a,int b,int c){
	return (c>a&&c<b)?1:0;
}
signed main(){
	int T=in;
	while(T--){
		clean();
		n=in,m=in;
		for(int i=1;i<=m;i++)
			a[i].a=in,a[i].b=in;	
		for(int i=1;i<=n;i++){
			q[i]=in;
			p[q[i]]=i;
			//p[i] 是 i 在環上的次序 
		}
		if(m>3*n-6){
			cout<<"NO"<<'\n';
			continue;
		}
		for(int i=1;i<=m;i++){
			a[i].a=p[a[i].a],a[i].b=p[a[i].b];
			if(a[i].a>a[i].b)
				swap(a[i].a,a[i].b);
			if(a[i].b-a[i].a!=1&&a[i].b-a[i].a!=n-1)
				ed[++tot]=i; 
		}
		for(int i=1;i<tot;i++)
			for(int j=i+1;j<=tot;j++){
				int xa=a[ed[i]].a,xb=a[ed[i]].b,ya=a[ed[j]].a,yb=a[ed[j]].b;
				//我們用一個端點在第一條線内而另一個端點不在來判斷，需要特判端點相同的情況 
				if(xa==ya||xa==yb||xb==ya||xb==yb)continue;
				if(cinab(xa,xb,ya)^cinab(xa,xb,yb)){
					insert(i,j+tot);
					insert(i+tot,j);
					insert(j,i+tot);
					insert(j+tot,i);
				}
			}
		for(int i=1;i<=tot*2;i++)if(!dfn[i])dfs(i);
		if(check())cout<<"YES"<<'\n';
		else cout<<"NO"<<'\n';	
	}
	return 0;
}