题目链接

BZOJ1997

题解

显然相交的两条边不能同时在圆的一侧，\(2-sat\)判一下就好了

但这样边数是\(O(m^2)\)的，无法通过此题

但是\(n\)很小，平面图 边数上界为\(3n – 6\)，所以过大的\(m\)可以判掉

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<map>
#define Redge(u) for (int k = h[u],to; k; k = ed[k].nxt)
#define REP(i,n) for (int i = 1; i <= (n); i++)
#define mp(a,b) make_pair<int,int>(a,b)
#define cls(s) memset(s,0,sizeof(s))
#define cp pair<int,int>
#define LL long long int
using namespace std;
const int maxn = 10005,maxm = 8000005,INF = 1000000000;
inline int read(){
int out = 0,flag = 1; char c = getchar();
while (c < 48 || c > 57){if (c == '-') flag = -1; c = getchar();}
while (c >= 48 && c <= 57){out = (out << 3) + (out << 1) + c - 48; c = getchar();}
return out * flag;
}
int h[maxn],ne;
struct EDGE{int to,nxt;}ed[maxm];
int n,m,N,pos[maxn],a[maxn],b[maxn],vis[maxn];
int dfn[maxn],low[maxn],Scc[maxn],st[maxn],scci,cnt,top;
inline void build(int u,int v){ed[++ne] = (EDGE){v,h[u]}; h[u] = ne;}
void dfs(int u){
dfn[u] = low[u] = ++cnt;
st[++top] = u;
Redge(u){
to = ed[k].to;
if (!dfn[to]){
dfs(to);
low[u] = min(low[u],low[to]);
}
else if (!Scc[to]) low[u] = min(low[u],dfn[to]);
}
if (dfn[u] == low[u]){
scci++;
do {
Scc[st[top]] = scci;
}while (st[top--] != u);
}
}
int main(){
int T = read();
while (T--){
n = read(); m = read();
REP(i,m) a[i] = read(),b[i] = read(),vis[i] = false;
REP(i,n) pos[read()] = i;
if (m > 3 * n - 6) {puts("NO"); continue;}
REP(i,m){
a[i] = pos[a[i]]; b[i] = pos[b[i]];
if (a[i] > b[i]) swap(a[i],b[i]);
if (a[i] + 1 == b[i]) vis[i] = true;
}
int tmp = m; m = 0;
REP(i,tmp) if (!vis[i]){
m++;
a[m] = a[i]; b[m] = b[i];
}
N = (m << 1); REP(i,N) h[i] = 0; ne = 0;
int x,y,xx,yy;
for (int i = 1; i <= m; i++){
x = a[i]; y = b[i];
for (int j = i + 1; j <= m; j++){
xx = a[j]; yy = b[j];
if ((x < xx && xx < y && yy > y) || (x < yy && yy < y && xx < x)){
build(i,j + m); build(j + m,i);
}
}
}
cnt = scci = top = 0;
REP(i,N) dfn[i] = low[i] = Scc[i] = 0;
REP(i,N) if (!dfn[i]) dfs(i);
int flag = true;
REP(i,m) if (Scc[i] == Scc[i + m]){
flag = false; break;
}
puts(flag ? "YES" : "NO");
}
return 0;
}