HNOI2010 平面圖判定（planar）

題目連結：戳我

我怎麼知道平面圖有這個性質？？

對于一個平面圖，它的邊數不超過點數的\(3n-6\)

是以可以直接把邊數多的特判掉，剩下的圖中邊數和點數就是一個數量級的了。

因為這個圖存在歐拉回路，是以我們先把那些構成歐拉回路的邊拉出來，将邊上的兩個端點的标号替換成在這個序列上的位置。然後判斷這些邊能不能不相交。

對于兩條邊\(i,j\)（分别對應\((u1,v1),(u2,v2)\)），如果\(u1<u2<v1<v2\)——

那麼這兩個邊肯定相交，不是平面圖！！

那麼這兩個邊肯定一個在環的内部，一個在外部。這種隻有兩種狀态進行規劃，判斷有沒有合法方案的題——顯然能想到2-SAT。

我們連四條邊，分别表示：

i在内部那麼j一定在外部
i在外部那麼j一定在内部
j在内部那麼i一定在外部
j在外部那麼i一定在内部

然後tarjan判斷一下有沒有同一條邊的兩個狀态在一個SCC裡即可。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#define MAXN 100010
using namespace std;
int n,m,t,tot,cnt,kkk,top,T;
int a[MAXN],b[MAXN],head[MAXN],pos[MAXN];
int dfn[MAXN],low[MAXN],in[MAXN],st[MAXN],c[MAXN];
struct Edge{int nxt,to,dis;}edge[MAXN<<1];
struct Line{int u,v;}line[MAXN<<1];
inline void add(int from,int to)
{
    // printf("[%d %d]\n",from,to);
    edge[++t].nxt=head[from],edge[t].to=to,head[from]=t;
}
inline void tarjan(int x)
{
    dfn[x]=low[x]=++tot;
    st[++top]=x;
    in[x]=1;
    for(int i=head[x];i;i=edge[i].nxt)
    {
        int v=edge[i].to;
        if(!dfn[v]) tarjan(v),low[x]=min(low[x],low[v]);
        else if(in[v]) low[x]=min(low[x],dfn[v]);
    }
    if(dfn[x]==low[x])
    {
        int v;
        cnt++;
        do{v=st[top--],in[v]=0,c[v]=cnt;}while(x!=v);
    }
}
inline bool check()
{
    for(int i=1;i<=m;i++)
        if(c[i]==c[i+m])
            return false;
    return true;
}
int main()
{
    #ifndef ONLINE_JUDGE
    freopen("ce.in","r",stdin);
    #endif
    scanf("%d",&T);
    while(T--)
    {
        memset(head,0,sizeof(head));
        memset(dfn,0,sizeof(dfn));
        memset(low,0,sizeof(low));
        memset(in,0,sizeof(in));
        tot=top=cnt=t=kkk=0;
        scanf("%d%d",&n,&m);
        for(int i=1;i<=m;i++) scanf("%d%d",&line[i].u,&line[i].v);
        for(int i=1;i<=n;i++) 
        {
            int x;
            scanf("%d",&x);
            pos[x]=i;
        }
        for(int i=1;i<=m;i++) line[i].u=pos[line[i].u],line[i].v=pos[line[i].v];
        if(m>3*n-6)
        {
            printf("NO\n");
            continue;
        }
        for(int i=1;i<=m;i++)
            if(abs(line[i].u-line[i].v)!=1)
            {
                line[++kkk]=line[i];
                if(line[kkk].u>line[kkk].v) swap(line[kkk].u,line[kkk].v);
            }
        m=kkk;
        for(int i=1;i<=m;i++)
            for(int j=1;j<=m;j++)
                if(line[i].u<line[j].u&&line[j].u<line[i].v&&line[j].v>line[i].v)
                    add(i+m,j),add(i,j+m),add(j,i+m),add(j+m,i);
        for(int i=1;i<=2*m;i++)
            if(!dfn[i])
                tarjan(i);
        // for(int i=1;i<=m;i++)
            // printf("%d %d\n",c[i],c[i+m]);
        if(check()==true) printf("YES\n");
        else printf("NO\n");
    }
    return 0;
}

轉載于:https://www.cnblogs.com/fengxunling/p/10884235.html