傳送門
題意：$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$元環将整個圖分成了兩個部分，一個在環内，一個在環外，而環内和環外連的邊不能在非頂點處相交。這個問題可以通過并查集來實作，将一條邊看做兩個點（一個表示不與目前邊排斥，一個表示與目前邊排斥），對于互相排斥的邊在并查集上合并，最後考慮是否存在一條邊的兩個點在一個集合内即可。
1 #include<bits/stdc++.h>
2 using namespace std;
3
4 inline int read(){
5 int a = 0;
6 bool f = 0;
7 char c = getchar();
8 while(!isdigit(c)){
9 if(c == '-')
10 f = 1;
11 c = getchar();
12 }
13 while(isdigit(c)){
14 a = (a << 3) + (a << 1) + (c ^ '0');
15 c = getchar();
16 }
17 return f ? -a : a;
18 }
19
20 struct Edge{
21 int start , end;
22 }Ed[10010];
23 map < int , int > lsh;
24 int N , M , cnt , fa[20010];
25
26 bool cmp(Edge a , Edge b){
27 return a.start < b.start;
28 }
29
30 inline void init(){
31 for(int i = 1 ; i <= M << 1 ; i++)
32 fa[i] = i;
33 }
34
35 int find(int x){
36 return fa[x] == x ? x : (fa[x] = find(fa[x]));
37 }
38
39 int main(){
40 #ifdef LG
41 freopen("3209.in" , "r" , stdin);
42 freopen("3209.out" , "w" , stdout);
43 #endif
44 for(int T = read() ; T ; T--){
45 N = read();
46 M = read();
47 for(int i = 1 ; i <= M ; i++){
48 Ed[i].start = read();
49 Ed[i].end = read();
50 }
51 lsh.clear();
52 for(int i = 1 ; i <= N ; i++)
53 lsh[read()] = i;
54 if(M > 3 * N - 6){
55 cout << "NO" << endl;
56 continue;
57 }
58 for(int i = 1 ; i <= M ; i++){
59 Ed[i].start = lsh[Ed[i].start];
60 Ed[i].end = lsh[Ed[i].end];
61 if(Ed[i].start > Ed[i].end)
62 swap(Ed[i].start , Ed[i].end);
63 }
64 init();
65 sort(Ed + 1 , Ed + M + 1 , cmp);
66 bool f = 1;
67 for(int i = 1 ; f && i <= M ; i++){
68 for(int j = i - 1 ; f && j ; j--)
69 if(Ed[j].end > Ed[i].start && Ed[j].end < Ed[i].end && Ed[j].start < Ed[i].start){
70 fa[find(j)] = find(i + M);
71 fa[find(i)] = find(j + M);
72 if(find(i) == find(i + M) || find(j) == find(j + M))
73 f = 0;
74 }
75 }
76 cout << (f ? "YES" : "NO") << endl;
77 }
78 return 0;
79 } 轉載于:https://www.cnblogs.com/Itst/p/9852151.html