【2-SAT(tarjan)】BZOJ1997-[Hnoi2010]Planar

时间:2023-12-09 13:05:13

【题目大意】
给出一张存在哈密顿回路的无向图,判断是否是平面图。
【思路】
首先平面图的一个性质:边数<=点数*3-6
因为存在哈密顿回路,可以将回路看作是一个圆,考量不再哈密顿回路中的边。如果两天边相交(判断相交可以随意yy一下),那么必然一条在圆内一条在圆外,显然是2-SAT。

 #include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<stack>
using namespace std;
const int MAXN=+;
int n,m;
int u[MAXN],v[MAXN],pos[MAXN];
vector<int> E[MAXN];
int dfn[MAXN],low[MAXN],instack[MAXN],col[MAXN],cnt,colcnt;
stack<int> S; int cross(int i,int j)
{
int x1=pos[u[i]],y1=pos[v[i]],x2=pos[u[j]],y2=pos[v[j]];
if ((x1<x2 && x2<y1 && y1<y2) || (x2<x1 && x1<y2 && y2<y1)) return ;else return ;
} void addedge(int u,int v)
{
E[u].push_back(v);
E[v].push_back(u);
} void tarjan(int u)
{
dfn[u]=low[u]=++cnt;
S.push(u);
instack[u]=; for (int i=;i<E[u].size();i++)
{
int son=E[u][i];
if (!instack[son])
{
tarjan(son);
low[u]=min(low[son],low[u]);
}
else
if (instack[son]==)
low[u]=min(dfn[son],low[u]);
} if (dfn[u]==low[u])
{
colcnt++;
int x;
do
{
x=S.top();
S.pop();
col[x]=colcnt;
instack[x]=;
}while (x!=u);
}
} void init()
{
scanf("%d%d",&n,&m);
cnt=,colcnt=;
for (int i=;i<MAXN;i++) vector<int>().swap(E[i]);//注意不要忘记清空
memset(instack,,sizeof(instack));
for (int i=;i<=m;i++)
scanf("%d%d",&u[i],&v[i]);
for (int i=;i<=n;i++)
{
int x;
scanf("%d",&x);
pos[x]=i;
}
} void build()
{
for (int i=;i<=m;i++)
if (pos[u[i]]>pos[v[i]]) swap(u[i],v[i]);
for (int i=;i<=m;i++)
for (int j=i+;j<=m;j++)
if (cross(i,j))
{
addedge(i,j+m);
addedge(i+m,j);
}
} void solve()
{
for (int i=;i<=*m;i++) if (!instack[i]) tarjan(i);
int f=;
for (int i=;i<=m;i++)
if (col[i]==col[i+m])
{
f=;
break;
}
if (f) cout<<"YES"<<endl;
else cout<<"NO"<<endl;
} int main()
{
int T;
scanf("%d",&T);
while (T--)
{
init();
if (m<=*n-)//平面图定理
{
build();
solve();
}
else
cout<<"NO"<<endl;
}
return ;
}