[bzoj1997][2-sat]Planar_综合

Description

Input

Output

Sample Input

2

6 9

1 4

1 5

1 6

2 4

2 5

2 6

3 4

3 5

3 6

1 4 2 5 3 6

5 5

1 2

2 3

3 4

4 5

5 1

1 2 3 4 5

Sample Output

NO

YES

题解

第一次做有关平面图的问题
先记下一个结论：对于一个极大简单平面图G(n,m)，总有m<=3*n-6
发现如果两条线段在圈内会相交，在圈外也会相交
暴力枚举两条线段判相交情况，建边2-sat判可行性
m很大但可以用上面那个结论剪枝
就愉快地 $n^2$ 啦

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
using namespace std;
struct pt{
   int c,op;}g[15];
bool cmp(pt n1,pt n2){
   return (n1.c!=n2.c)?(n1.c<n2.c):(n1.op<n2.op);}
struct edge{
   int x,y;}w[10005];
struct node{
   int x,y,next;}a[400005];int len,last[1205];
void ins(int x,int y){len++;a[len].x=x;a[len].y=y;a[len].next=last[x];last[x]=len;}
int low[1205],dfn[1205],sta[1205],belong[1205],id,cnt,tp,n,m;
bool v[1205];
void tarjan(int x)
{low[x]=dfn[x]=++id;sta[++tp]=x;v[x]=true;for(int k=last[x];k;k=a[k].next){int y=a[k].y;if(dfn[y]==-1)tarjan(y),low[x]=min(low[x],low[y]);else if(v[y])low[x]=min(low[x],dfn[y]);}if(low[x]==dfn[x]){int i;cnt++;do{i=sta[tp--];belong[i]=cnt;v[i]=false;}while(i!=x);}
}
int ring[1205],pos[1205];
bool check(int x,int y)
{int u=pos[x];if(ring[u+1]!=y&&ring[u-1]!=y)return true;return false;
}
int main()
{int T;scanf("%d",&T);while(T--){scanf("%d%d",&n,&m);for(int i=1;i<=m;i++)scanf("%d%d",&w[i].x,&w[i].y);for(int i=1;i<=n;i++)scanf("%d",&ring[i]),pos[ring[i]]=i;ring[0]=ring[n];ring[n+1]=ring[1];if(m>3*n-6){
   puts("NO");continue;}len=0;memset(last,0,sizeof(last));for(int i=1;i<=m;i++)if(check(w[i].x,w[i].y))for(int j=i+1;j<=m;j++)if(check(w[j].x,w[j].y)){int s1=pos[w[i].x],s2=pos[w[i].y];if(s1>s2)swap(s1,s2);int s3=pos[w[j].x],s4=pos[w[j].y];if(s3>s4)swap(s3,s4);if(s1==s3||s1==s4||s2==s3||s2==s4)continue;g[1].c=s1;g[1].op=1;g[2].c=s2;g[2].op=1;g[3].c=s3;g[3].op=2;g[4].c=s4;g[4].op=2;sort(g+1,g+1+4,cmp);if(g[1].op==g[3].op)ins(i,j+m),ins(i+m,j),ins(j,i+m),ins(j+m,i);}memset(dfn,-1,sizeof(dfn));memset(low,0,sizeof(low));memset(v,false,sizeof(v));id=cnt=tp=0;for(int i=1;i<=2*m;i++)if(dfn[i]==-1)tarjan(i);bool bk=true;for(int i=1;i<=m;i++)if(belong[i]==belong[i+m]){bk=false;break;}if(bk)puts("YES");else puts("NO");}return 0;
}