平面圖 / 平面圖判定
題目連結：ybt金牌導航3-6-5 / luogu P3209
題目大意
給你一個圖，保證圖存在哈密頓路徑（即圖中存在一個包含所有頂點的環），且給出。
問你它是否是一個平面圖。
如果能将一個無向圖畫在平面上使得每兩個無重合頂點的邊都不會相交，那這個圖就是平面圖。
思路
我們看到這個東西似乎沒有思路，考慮把樣例的兩個圖搞出來：
第二個可以這非常明顯，但為什麼第一個不行呢？
你會發現把哈密頓路徑的邊去掉，裡面的邊無論怎麼搞都會交在一起。
那你就會想你是不是判斷一下裡面的會不會交在一起就可以了。
至于怎麼判斷，我們可以先按哈密頓路徑把點重新編号。
那考慮到如果兩條邊 ( a , b ) (a,b) (a,b) 和 ( c , d ) (c,d) (c,d) 有交點，那它們會滿足這樣的關系： a < c < b < d a<c<b<d a<c<b<d
簡稱把環搞成一條鍊之後着兩條邊有重合的部分。（當然 c < a < d < b c<a<d<b c<a<d<b 也行）
但是你以為這樣就結束了？
我們把原來不行的樣例中 ( 3 , 4 ) (3,4) (3,4) 這條邊去掉。
你以為它不行，但它其實可以這樣：
什麼意思呢？就是它連不是哈密頓的邊的時候不一定要連在環的裡面，它是可以在外面連的！
那就相當于對于一條不在哈密頓路徑上的邊，它可以在裡面連，也可以在外面連，那原來的相交關系隻要用這兩個邊一個裡面一個外面就不會影響。
那也就說如果兩個邊之間有沖突關系，那一個選了裡面另一個就一定要外面，一個選了外面另一個就一定要在裡面。
然後你發現它就是 2-sat。
但是你會發現你不是哈密頓距離上的邊太多了，大概是 1 0 4 10^4 104 級别，你兩兩之間判斷是否相交就炸了啊。
這時候就要用到平面圖的性質了。
要用到的性質是如果一個圖是平面圖，點的個數是 n n n，邊的個數是 m m m，則一定滿足 m ≤ 3 × n − 6 m\leq3\times n-6 m≤3×n−6。
關于這裡的證明就不多講了，可以去看看一個 PPT。
圖論4-6 平面圖
（當然你上網直接搜也應該搜得到）
然後你就直接判斷，如果 m > 3 × n − 6 m>3\times n-6 m>3×n−6 就直接是
NO
。
那你的 m m m 就變成了 1 0 2 ∼ 1 0 3 10^2\sim10^3 102∼103 級别的，就可以 m 2 m^2 m2 搞了。
代碼
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
struct node {
int to, nxt;
}e[5000001];
int T, n, m, x, y, dy[10001];
int v[10001], lx[10001], ly[10001];
int le[10001], KK, low[10001], dfn[10001];
int tmp, tot, sta[10001], in[10001];
bool a[501][501], yes;
void csh() {
memset(a, 0, sizeof(a));
KK = 0;
memset(le, 0, sizeof(le));
memset(dfn, 0, sizeof(dfn));
tmp = 0;
tot = 0;
memset(in, 0, sizeof(in));
}
void add(int x, int y) {
e[++KK] = (node){y, le[x]}; le[x] = KK;
}
void tarjan(int now) {
dfn[now] = low[now] = ++tmp;
sta[++sta[0]] = now;
for (int i = le[now]; i; i = e[i].nxt)
if (!dfn[e[i].to]) {
tarjan(e[i].to);
low[now] = min(low[now], low[e[i].to]);
}
else if (!in[e[i].to]) low[now] = min(low[now], low[e[i].to]);
if (dfn[now] == low[now]) {
in[now] = ++tot;
while (sta[sta[0]] != now) {
in[sta[sta[0]]] = tot;
sta[0]--;
}
sta[0]--;
}
}
int main() {
scanf("%d", &T);
while (T--) {
csh();
scanf("%d %d", &n, &m);
for (int i = 1; i <= m; i++) {
scanf("%d %d", &x, &y);
a[x][y] = 1;
a[y][x] = 1;
}
for (int i = 1; i <= n; i++) {
scanf("%d", &v[i]);
dy[v[i]] = i;
}
if (n * 3 - 6 < m) {//平面圖定理
printf("NO\n");
continue;
}
v[n + 1] = v[1];
for (int i = 1; i <= n; i++)
a[v[i]][v[i + 1]] = a[v[i + 1]][v[i]] = 0;
m = 0;//找到不在哈密頓路徑上的邊
for (int i = 1; i <= n; i++)
for (int j = 1; j < i; j++)
if (a[i][j]) {
m++;
lx[m] = i;
ly[m] = j;
if (dy[lx[m]] > dy[ly[m]]) swap(lx[m], ly[m]);
}
for (int i = 1; i <= m; i++)//判斷這些邊之間那些會相交（相交就不能同時擺在裡面 / 外面）
for (int j = 1; j < i; j++)
if (dy[lx[i]] < dy[lx[j]] && dy[lx[j]] < dy[ly[i]] && dy[ly[i]] < dy[ly[j]]) {
add(i, m + j);
add(j, m + i);
add(m + i, j);
add(m + j, i);
}
else if (dy[lx[j]] < dy[lx[i]] && dy[lx[i]] < dy[ly[j]] && dy[ly[j]] < dy[ly[i]]) {
add(i, m + j);
add(j, m + i);
add(m + i, j);
add(m + j, i);
}
for (int i = 1; i <= m + m; i++)
if (!dfn[i]) tarjan(i);
yes = 1;
for (int i = 1; i <= m; i++)
if (in[i] == in[m + i]) {
yes = 0;
break;
}
if (yes) printf("YES\n");
else printf("NO\n");
}
return 0;
}