题意：$T$组数据，每组数据给出一个$N$个点，$M$条边，并存在一个$N$元环的图，试判断其是否为一个可平面图（如果存在一种画法，使得该图与给出的图同构且边除了在顶点处以外互相不相交，则称其为可平面图）$T \leq 100 , N \leq 200 , M \leq 10000$
关于平面图的性质可以参照这一个PPT
我们需要用到平面图的一个推论：在极大平面图（不能再加边的平面图）上，$M = 3 \times N - 6$（PPT里面有证明）
所以对于$M > 3 \times N - 6$的情况可以直接判定为NO，这样我们需要处理的问题的边数变为了$O(N)$级别。
接下来我们考虑$N$元环的作用。一个$N$元环将整个图分成了两个部分，一个在环内，一个在环外，而环内和环外连的边不能在非顶点处相交。这个问题可以通过并查集来实现，将一条边看做两个点（一个表示不与当前边排斥，一个表示与当前边排斥），对于互相排斥的边在并查集上合并，最后考虑是否存在一条边的两个点在一个集合内即可。
#include<bits/stdc++.h>
using namespace std;
inline int read(){
;
;
char c = getchar();
while(!isdigit(c)){
if(c == '-')
f = ;
c = getchar();
}
while(isdigit(c)){
a = (a << ) + (a << ) + (c ^ ');
c = getchar();
}
return f ? -a : a;
}
struct Edge{
int start , end;
}Ed[];
map < int , int > lsh;
];
bool cmp(Edge a , Edge b){
return a.start < b.start;
}
inline void init(){
; i <= M << ; i++)
fa[i] = i;
}
int find(int x){
return fa[x] == x ? x : (fa[x] = find(fa[x]));
}
int main(){
#ifdef LG
freopen("3209.in" , "r" , stdin);
freopen("3209.out" , "w" , stdout);
#endif
for(int T = read() ; T ; T--){
N = read();
M = read();
; i <= M ; i++){
Ed[i].start = read();
Ed[i].end = read();
}
lsh.clear();
; i <= N ; i++)
lsh[read()] = i;
* N - ){
cout << "NO" << endl;
continue;
}
; i <= M ; i++){
Ed[i].start = lsh[Ed[i].start];
Ed[i].end = lsh[Ed[i].end];
if(Ed[i].start > Ed[i].end)
swap(Ed[i].start , Ed[i].end);
}
init();
sort(Ed + , Ed + M + , cmp);
;
; f && i <= M ; i++){
; f && j ; j--)
if(Ed[j].end > Ed[i].start && Ed[j].end < Ed[i].end && Ed[j].start < Ed[i].start){
fa[find(j)] = find(i + M);
fa[find(i)] = find(j + M);
if(find(i) == find(i + M) || find(j) == find(j + M))
f = ;
}
}
cout << (f ? "YES" : "NO") << endl;
}
;
}