HNOI2010 平面圖判定

對于這個題，我們隻需要判斷是否為平面圖。

我們發現他給了我們一個很好的性質：那就是這個平面圖上存在着一個哈密頓回路（ｎ元環）。

那麼我們就可以很簡單的判定兩條邊　如果劃在同一側是否會相交。

如果相交，那麼我們就得把他們放在兩側，否則不需要。

然後隻需判斷是否在滿足所有條件的前提下出現了沖突就行了。

要解決這個東西，并查集很擅長，但是這裡用建圖縮點解決。

對于一條邊i,隻有可能裡外兩側，分别記為di,di'。

那麼對于兩條需要異側的邊i，j，我們隻需連上無向邊（di, dj'），(dj, di')。

然後我們可以對于每一個需要滿足的條件，建出一個圖，

縮點後，如果同一個強連通分量中存在di,di'那麼就不是。

最後最好加上一條平面圖的性質優化一下。

就是平面圖的　邊數不超過點數*3-6。

#include <string>
#include <cstdio>
#include <cstring>
#define RG register
#define Swap(a,b) a^=b,b^=a,a^=b
using namespace std;

inline int gi () {
    int x=0,w=0; char ch=0;
    while (ch<'0' || ch>'9') {if (ch=='-') w=1; ch=getchar ();}
    while (ch>='0' && ch<='9') x=(x<<3)+(x<<1)+(ch^48), ch=getchar ();
    return w?-x:x;
}

const int N=410;
const int M=1e5+10;

int tot,head[M<<1],to[M<<2],Next[M<<2];
int T,n,m,num,u[M],v[M],Ex[M],Ey[M],a[N][N],pos[M];
int Time,cnt,top,ins[M<<1],dfn[M<<1],low[M<<1],sta[M<<1],Bel[M<<1];

inline void New_case () {
    Time=tot=cnt=top=num=0;
    memset (a, 0, sizeof (a));
    memset (pos, 0, sizeof (pos));
    memset (ins, 0, sizeof (ins));
    memset (dfn, 0, sizeof (dfn));
    memset (low, 0, sizeof (low));
    memset (Bel, 0, sizeof (Bel));
    memset (head, 0, sizeof (head));
    memset (to, 0, sizeof (to));
    memset (Next, 0, sizeof (Next));
}

inline void make (int from, int To) {
    Next[++tot]=head[from];
    head[from]=tot;
    to[tot]=To;
}

inline bool cross (int a, int b) {
    RG int fr1=pos[Ex[a]],fr2=pos[Ex[b]],tt1=pos[Ey[a]],tt2=pos[Ey[b]];
    if (fr1>tt1) Swap (fr1, tt1); if (fr2>tt2) Swap (fr2, tt2);
    if (fr1<fr2 && tt1<tt2 && tt1>fr2) return 1;
    if (fr1>fr2 && tt1>tt2 && tt2>fr1) return 1;
    return 0;
}

void Tarjan (int x) {
    dfn[x]=low[x]=++Time;
    sta[++top]=x, ins[x]=1;
    for (RG int i=head[x],y;i;i=Next[i]) {
        y=to[i];
        if (!dfn[y]) Tarjan (y), low[x]=min (low[x], low[y]);
        else if (ins[y]) low[x]=min (low[x], dfn[y]);
    }
    if (low[x]==dfn[x]) {
        ++cnt;
        RG int k;
        do {
            k=sta[top--], ins[k]=0, Bel[k]=cnt;
        }while (k!=x);
    }
}

inline bool check () {
    for (RG int i=1;i<=num;++i)
        if (Bel[i]==Bel[i+m]) return 0;
    return 1;
}

int main ()
{
    RG int i,j,fir,x,y;
    T=gi ();
    while (T--) {
        New_case ();
        n=gi (), m=gi ();
        for (i=1;i<=m;++i) u[i]=gi (), v[i]=gi ();
        x=fir=gi (), pos[x]=1;
        for (i=2;i<=n;++i) y=gi (), pos[y]=i, a[x][y]=a[y][x]=1, x=y;
        a[fir][x]=a[x][fir]=1;
        if (m>3*n-6) {
            puts ("NO");
            continue;
        }
        for (i=1;i<=m;++i)
            if (!a[u[i]][v[i]]) Ex[++num]=u[i], Ey[num]=v[i];
        for (i=1;i<=num;++i)
            for (j=i+1;j<=num;++j)
                if (cross (i,j))
                    make (i, j+m), make (j+m, i), make (j, i+m), make (i+m, j);
        for (i=1;i<=num+m;++i)
            if (!dfn[i]) Tarjan (i);
        check ()?puts ("YES"):puts ("NO");
    }
    return 0;
}      

轉載于:https://www.cnblogs.com/Bhllx/p/9864999.html