[bzoj1997][Hnoi2010]平面圖判定——2-SAT+平面圖定理

題目大意：

給定一個帶有哈密頓回路的圖，求此圖是否為平面圖。

思路：

既然有哈密頓回路，則可以把環外和環内看成兩個不同的區域，然後如果有不是環上的邊相交的話就不能同時在環内或者環外。然後就可以轉化為2-SAT模型。

但是發現如果枚舉去連邊的話顯然很可能會TLE。這個時候要用到平面圖的一個定理，即任意一個平面圖的邊的個數不大于3*n-6，至于證明我就不知道了。。

然後就直接枚舉連邊跑2-SAT就好了。

#include<bits/stdc++.h>

#define REP(i,a,b) for(int i=a;i<=b;++i)
#define pii pair<int,int>
#define fi first
#define se second
#define mk make_pair
typedef long long ll;

using namespace std;

void File(){
    freopen("bzoj1997.in","r",stdin);
    freopen("bzoj1997.out","w",stdout);
}

template<typename T>void read(T &_){
    T __=,mul=; char ch=getchar();
    while(!isdigit(ch)){
        if(ch=='-')mul=-;
        ch=getchar();
    }
    while(isdigit(ch))__=(__<<)+(__<<)+(ch^'0'),ch=getchar();
    _=__*mul;
}

const int maxn=+;
const int maxm=+;
int T,n,m,a[maxn],pos[maxn];
pii E[maxm];
vector<int>G[maxn*];

void init(){
    read(n); read(m);
    int u,v;
    REP(i,,m)read(u),read(v),E[i]=mk(u,v);
    REP(i,,n)read(a[i]),pos[a[i]]=i;
    REP(i,,m){
        E[i].fi=pos[E[i].fi]; E[i].se=pos[E[i].se];
        if(E[i].fi>E[i].se)swap(E[i].fi,E[i].se);
        //cout<<E[i].fi<<" "<<E[i].se<<endl;
    }
}

void build_map(){
    REP(i,,m*)G[i].clear();
    REP(i,,m)REP(j,i+,m){
        if(E[i].fi<=E[j].fi && E[i].se>=E[j].se)continue;
        if(E[i].fi>=E[j].fi && E[i].se<=E[j].se)continue;
        if(E[i].se<=E[j].fi || E[j].se<=E[i].fi)continue;
        //cout<<i<<" "<<j<<endl;//" "<<E[i].fi<<" "<<E[i].se<<" "<<E[j].fi<<" "<<E[j].se<<endl;
        G[i].push_back(j+m);
        G[j].push_back(i+m);
        G[i+m].push_back(j);
        G[j+m].push_back(i);
        //cout<<i<<" "<<j+m<<endl;
        //cout<<j<<" "<<i+m<<endl;
    }
    //cout<<"--------------------"<<endl;
}

int low[maxm*],dfn[maxm*],cnt_dfn,cnt_scc,bel[maxm*];
stack<int>stk;

void tarjan(int u){
    low[u]=dfn[u]=++cnt_dfn;
    stk.push(u);
    for(int sz=G[u].size()-,i=;i<=sz;++i){
        int v=G[u][i];
        if(!dfn[v]){
            tarjan(v);
            low[u]=min(low[u],low[v]);
        }
        else if(!bel[v])low[u]=min(low[u],dfn[v]);
    }
    if(dfn[u]==low[u]){
        ++cnt_scc;
        for(int p=;p!=u;stk.pop()){
            p=stk.top();
            //cout<<p<<" ";
            bel[p]=cnt_scc;
        }
        //cout<<endl;
    }
}

bool work(){
    cnt_dfn=cnt_scc=;
    memset(low,,sizeof(low));
    memset(dfn,,sizeof(dfn));
    memset(bel,,sizeof(bel));
    REP(i,,m*)if(!dfn[i])
        tarjan(i);
    REP(i,,m)if(bel[i]==bel[i+m])
        return false;
    return true;
}

int main(){
    File();
    read(T);
    while(T--){
        init();
        if(m>*n-){
            puts("NO");
            continue;
        }
        build_map();
        work() ? puts("YES") : puts("NO");
    }
    return ;
}