[BZOJ1997][Hnoi2010]Planar 2-sat （联通分量） 平面图

1997: [Hnoi2010]Planar

Time Limit: 10 Sec  Memory Limit: 64 MB
Submit: 2317  Solved: 850
[Submit][Status][Discuss]

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

HINT

 

Source

Day1

太强辣。

平面图的边数不大于3*n-6剪枝。

先将环提出来，对于剩下的边，我们可以选择在环外连还是在环内连。

对于不相交的边，显然在环外连和在环内连都不会相交。

对于相交的边，显然不能同时在环外连或在环内连。只能一个在环外一个在环内。

将一条边拆为环外、环内两条边，构造2-sat。

判断2*i和2*i-1是否在同一个联通分量里。

 #include<iostream>

 #include<cstring>

 #include<cstdlib>

 #include<cstdio>

 #include<cmath>

 #include<algorithm>

 #include<queue>

 #define LL long long

 #define mod 19650827

 using namespace std;

 int read() {

     char ch=getchar();int x=,f=;

     while(!isdigit(ch)){ch=getchar();}

     while(isdigit(ch)){x=x*+ch-'';ch=getchar();}

     return x;

 }

 int T;

 int n,m;

 struct data {

     int u,v;

 }a[];

 int pos[];

 int cnt=;

 int head[],cntt;

 struct edge {

     int to,next;

 }e[];

 void add(int u,int v) {e[cntt].to=v;e[cntt].next=head[u];head[u]=cntt++;}

 int dfn[],low[],inq[],sz;

 int sta[],top,bl[],scc;

 void tarjan(int now) {

     dfn[now]=low[now]=++sz;

     sta[++top]=now;inq[now]=;

     for(int i=head[now];i>=;i=e[i].next) {

         int to=e[i].to;

         if(!dfn[to]) {tarjan(to);low[now]=min(low[now],low[to]);}

         else if(inq[to]) {low[now]=min(low[now],dfn[to]);}

     }

     if(low[now]==dfn[now]) {

         int x=-;

         scc++;

         while(x!=now) {

             x=sta[top--];inq[x]=;

             bl[x]=scc;

         }

     }

 }

 int main() {

     T=read();

     while(T--) {

         cnt=;cntt=;top=;scc=;sz=;

         memset(head,-,sizeof(head));

         memset(dfn,,sizeof(dfn));memset(low,,sizeof(low));

         memset(inq,,sizeof(inq));

         n=read(),m=read();

         for(int i=;i<=m;i++) a[i].u=read(),a[i].v=read();

         for(int i=;i<=n;i++) pos[read()]=i;

         if(m>*n-){printf("NO\n");continue;}

         for(int i=;i<=m;i++) {

             int c=abs(pos[a[i].u]-pos[a[i].v]);

             if(c==||(max(pos[a[i].u],pos[a[i].v])==n&&min(pos[a[i].u],pos[a[i].v])==)) continue;

             a[++cnt]=a[i];

         }

         for(int i=;i<=cnt;i++) {

             for(int j=i+;j<=cnt;j++) {

                 int t1=pos[a[i].u],t2=pos[a[i].v];

                 if(t1>t2) swap(t1,t2);

                 int t3=pos[a[j].u],t4=pos[a[j].v];

                 if(t3>t4) swap(t3,t4);

                 if((t1<t3&&t2<t4&&t2>t3)||(t1>t3&&t2>t4&&t1<t4)) {

                     add(*i-,*j);add(*j,*i-);

                     add(*i,*j-);add(*j-,*i);

                 }

             }

         }

         for(int i=;i<=*cnt;i++) if(!dfn[i]) tarjan(i);

         bool flag=;

         for(int i=;i<=cnt;i++) if(bl[*i]==bl[*i-]){printf("NO\n");flag=;break;}

         if(flag)printf("YES\n");

     }

 }