题目大意
给定一个 $n$ 个结点 $m$ 条边的无向图，保证它有哈密尔顿回路。给定它的一个哈密尔顿回路，问它是不是平面图。
数据范围：$T \le 100, n \le 200, m \le 10^4$。
思路分析
把哈密尔顿回路看作是一个环，其他边看作是环上的一条弦。对于每一条弦，我们要么把它放在环的外面，要么把它放在里面。如果两条弦不相交，那么随便放；否则它们不能在圆的同一侧。于是使用 2 - SAT 来判断是否有解即可。
这样的复杂度还不够优秀，我们考虑优化。发现平面图满足 $m \le 3n - 6$，所以我们加入剪枝即可把复杂度优化到 $O(Tn^2)$。注意 2 - SAT 上表示两个变量取值不相同需要联结四条有向边，而不是一条或两条。
代码实现
1 | |
2 | |
3 | |
4 | using namespace std; |
5 | |
6 | const int maxn = 1e4; |
7 | int T, n, m, a[maxn + 3], k, u[maxn + 3], v[maxn + 3], rnk[maxn + 3]; |
8 | int tm, dfn[maxn + 3], low[maxn + 3], top, st[maxn + 3], cnt, bel[maxn + 3]; |
9 | bool in[maxn + 3]; |
10 | vector<int> G[maxn + 3]; |
11 | |
12 | void add(int u, int v) { |
13 | G[u].push_back(v); |
14 | } |
15 | |
16 | void tarjan(int u) { |
17 | dfn[u] = low[u] = ++tm; |
18 | st[++top] = u, in[u] = true; |
19 | for (int i = 0, v; i < G[u].size(); i++) { |
20 | v = G[u][i]; |
21 | if (!dfn[v]) { |
22 | tarjan(v); |
23 | low[u] = min(low[u], low[v]); |
24 | } else if (in[v]) { |
25 | low[u] = min(low[u], dfn[v]); |
26 | } |
27 | } |
28 | if (low[u] == dfn[u]) { |
29 | ++cnt; |
30 | do { |
31 | bel[st[top]] = cnt; |
32 | in[st[top]] = false; |
33 | } while (st[top--] != u); |
34 | } |
35 | } |
36 | |
37 | int main() { |
38 | scanf("%d", &T); |
39 | while (T--) { |
40 | for (int i = 1; i <= k * 2; i++) { |
41 | vector<int> t; |
42 | swap(G[i], t); |
43 | dfn[i] = 0; |
44 | } |
45 | k = 0; |
46 | scanf("%d %d", &n, &m); |
47 | for (int i = 1; i <= m; i++) { |
48 | scanf("%d %d", &u[i], &v[i]); |
49 | } |
50 | for (int i = 1; i <= n; i++) { |
51 | scanf("%d", &a[i]); |
52 | rnk[a[i]] = i; |
53 | } |
54 | if (m > 3 * n - 6) { |
55 | puts("NO"); |
56 | continue; |
57 | } |
58 | for (int i = 1; i <= m; i++) { |
59 | int x = rnk[u[i]], y = rnk[v[i]]; |
60 | if (x > y) { |
61 | swap(x, y); |
62 | } |
63 | if ((x == 1 && y == n) || x == y - 1) { |
64 | continue; |
65 | } |
66 | u[++k] = x, v[k] = y; |
67 | } |
68 | for (int i = 1; i <= k; i++) { |
69 | for (int j = i + 1; j <= k; j++) { |
70 | if (u[i] >= u[j] && u[i] <= v[j] && v[i] >= u[j] && v[i] <= v[j]) { |
71 | continue; |
72 | } |
73 | if ((u[i] <= u[j] || u[i] >= v[j]) && (v[i] <= u[j] || v[i] >= v[j])) { |
74 | continue; |
75 | } |
76 | add(i, j + k); |
77 | add(j, i + k); |
78 | add(i + k, j); |
79 | add(j + k, i); |
80 | } |
81 | } |
82 | tm = 0, cnt = 0; |
83 | for (int i = 1; i <= k * 2; i++) { |
84 | if (!dfn[i]) { |
85 | tarjan(i); |
86 | } |
87 | } |
88 | bool flag = true; |
89 | for (int i = 1; i <= k; i++) { |
90 | if (bel[i] == bel[i + k]) { |
91 | flag = false; |
92 | break; |
93 | } |
94 | } |
95 | puts(flag ? "YES" : "NO"); |
96 | } |
97 | return 0; |
98 | } |