給一張$n$個節點的無向圖，再給$m$組$(a,b)$，代表$a$跟$b$之間有一條邊，問該圖是否為一棵合法二元搜索樹。
$1\le n\le 1000, 1\le m\le \frac{n(n-1)}{2}$
分兩步驟，先確定她是一棵樹，再確認他是不是二元搜索樹。
樹只要滿足兩個條件:邊數==點數-1且任一一點dfs會遍歷所有點，但這裡的邊數要扣掉重邊，以題目敘述來說重邊要算同一條。
二元搜索樹有個性質:中序遍歷產生的序列會是排序好的，所以只要枚舉所有點當根來遍歷看看，稍微處理子節點數量超過兩個或者無法分成左右節點的情況就好。
複雜度$\mathcal{O}(n^2)$
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
|
#include <bits/stdc++.h>
using namespace std;
#define EmiliaMyWife ios::sync_with_stdio(0); cin.tie(NULL);
using ll = int64_t;
using ull = uint64_t;
using ld = long double;
using uint = uint32_t;
const double EPS = 1e-8;
const int INF = 0x3F3F3F3F;
const ll LINF = 4611686018427387903;
const int MOD = 1e9+7;
void no() { cout << "NO\n"; exit(0); }
signed main() { EmiliaMyWife
int n, m;
cin >> n >> m;
vector<vector<int>> edge(n + 1);
vector<int> arr(n + 1);
for(int i = 1; i <= n; i++)
cin >> arr[i];
set<pair<int, int>> has;
int w = 0;
for(int i = 0, a, b; i < m; i++) {
cin >> a >> b;
if(a > b)
swap(a, b);
if(has.count({a, b}))
continue;
w++;
has.insert({a, b});
edge[a].push_back(b);
edge[b].push_back(a);
}
if(w != n - 1)
no();
vector<bool> vis(n + 1);
const function<void(int)> dfs = [&] (int u) {
if(vis[u])
return;
vis[u] = 1;
for(int v : edge[u])
dfs(v);
};
dfs(1);
for(int i = 1; i <= n; i++)
if(!vis[i])
no();
vector<int> owo;
const function<bool(int, int)> bst = [&] (int u, int p) {
int l = 0, r = 0;
for(int v : edge[u]) {
if(v == p)
continue;
if(arr[v] >= arr[u]) {
if(r)
return false;
r = v;
}
else {
if(l)
return false;
l = v;
}
}
bool ok = 1;
if(l)
ok &= bst(l, u);
owo.push_back(arr[u]);
if(r)
ok &= bst(r, u);
return ok;
};
bool ok = 0;
for(int i = 1; i <= n; i++) {
owo.clear();
ok |= (bst(i, i) && is_sorted(owo.begin(), owo.end()));
}
if(!ok)
no();
cout << "YES\n";
}
|