Description:
若能将无向图 (G=(V, E)) 画在平面上使得任意两条无重合顶点的边不相交，则称 (G) 是平面图。判定一个图是否为平面图的问题是图论中的一个重要问题。现在假设你要判定的是一类特殊的图，图中存在一个包含所有顶点的环，即存在哈密顿回路。输入输出格式输入格式：
输入文件的第一行是一个正整数 (T)，表示数据组数 (每组数据描述一个需要判定的图)。接下来从输入文件第二行开始有 (T) 组数据，每组数据的第一行是用空格隔开的两个正整数 (N) 和 (M)，分别表示对应图的顶点数和边数。紧接着的 (M) 行，每行是用空格隔开的两个正整数 (u) 和 (v) (left(1leq u,vleq N ight))，表示对应图的一条边 (left(u,v ight)), 输入的数据保证所有边仅出现一次。每组数据的最后一行是用空格隔开的 (N) 个正整数，从左到右表示对应图中的一个哈密顿回路：(V_1,V_2,…,V_N)，即对任意 (i ot=j) 有 (V_i ot=V_j) 且对任意 (1leq ileq N-1) 有 (left(V_i,V_i-1 ight)in E) 及 (left(V_1,V_N ight)in E)。
输入的数据保证 (100\%) 的数据满足 (Tleq100,3leq Nleq200,Mleq10000).
Solution:
即判断是否可以让这些边都不相交
对于环上的四个点,设它们的序号依次为 (a_1,a_2,a_3,a_4)
若两条边为 (a_1-a_2) 和 (a_3-a_4)
显然他们不会相交
若为 (a_1-a_3) 和 (a_2-a_4)
则只有当一条边在回路外,一条边在回路内时,方可不相交
这样,(2-SAT)的模型就建出来了
详见代码:
#include <map>
#include <set>
#include <stack>
#include <cmath>
#include <queue>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#define ls p<<1
#define rs p<<1|1
using namespace std;
typedef long long ll;
const int mxn=1e6+5;
int n,m,T,p,tot,cnt,col;
int c[mxn],x[mxn],y[mxn],hd[mxn],ex[mxn],ey[mxn],bl[mxn],vis[mxn],dfn[mxn],ins[mxn],low[mxn],cir[mxn],f[2000][2000];
stack<int > st;
inline int read() {
char c=getchar(); int x=0,f=1;
while(c>'9'||c<'0') {if(c=='-') f=-1;c=getchar();}
while(c<='9'&&c>='0') {x=(x<<3)+(x<<1)+(c&15);c=getchar();}
return x*f;
}
inline void chkmax(int &x,int y) {if(x<y) x=y;}
inline void chkmin(int &x,int y) {if(x>y) x=y;}
struct ed {
int to,nxt;
}t[mxn];
inline void add(int u,int v) {
t[++cnt]=(ed) {v,hd[u]}; hd[u]=cnt;
}
void tj(int u)
{
dfn[u]=low[u]=++p; st.push(u); ins[u]=1;
for(int i=hd[u];i;i=t[i].nxt) {
int v=t[i].to;
if(!dfn[v]) tj(v),chkmin(low[u],low[v]);
else if(ins[v]) chkmin(low[u],dfn[v]);
}
if(low[u]==dfn[u]) {
++col;
do {
bl[u]=col; u=st.top();
st.pop(); ins[u]=0;
} while(low[u]!=dfn[u]);
}
}
int check() {
for(int i=1;i<=m*2;++i)
if(!dfn[i]) tj(i);
for(int i=1;i<=m;++i)
if(bl[i]==bl[i+m]) return 0;
return 1;
}
void solve()
{
cnt=tot=col=p=0; int a,b;
memset(hd,0,sizeof(hd));
memset(dfn,0,sizeof(dfn));
memset(low,0,sizeof(low));
memset(bl,0,sizeof(bl));
memset(f,0,sizeof(f));
n=read(); m=read();
for(int i=1;i<=m;++i) {
x[i]=read(); y[i]=read();
if(x[i]>y[i]) swap(x[i],y[i]);
}
for(int i=1;i<=n;++i) {
c[i]=read(); vis[c[i]]=i;
if(i>1) {
int a=c[i-1],b=c[i];
if(a<b) f[a][b]=1;
else f[b][a]=1;
}
}
if(m>3*n-6) {
puts("NO"); //这里是一个结论,若不满足则直接判掉
return ; //由于我太菜了,所以不会证明
}
a=c[n],b=c[1];
if(a<b) f[a][b]=1;
else f[b][a]=1;
for(int i=1;i<=m;++i) {
if(f[x[i]][y[i]]) continue ; //是环上的边,就不管它
ex[++tot]=x[i],ey[tot]=y[i];
}
m=tot; int u,v,w,z;
for(int i=1;i<m;++i) {
for(int j=i+1;j<=m;++j) {
u=vis[ex[i]],v=vis[ey[i]],w=vis[ex[j]],z=vis[ey[j]];
if(u>v) swap(u,v); if(w>z) swap(w,z);
if((u<w&&v>w&&v<z)||(u>w&&u<z&&v>z)) {
add(i,j+m); add(i+m,j); //连边
add(j,i+m); add(j+m,i); //内->外 外->内
}
}
}
printf(check()?"YES
":"NO
");
}
int main()
{
T=read();
while(T--) solve();
return 0;
}