Havel-Hakimi & Erdős-Gallai 定理
stripe_python · · 算法·理论
用于判定无向图的度数序列是否可简单图化。简单图化的意思是,存在一个
Havel-Hakimi 定理
考虑度数序列
Erdős-Gallai 定理
考虑降序排序的度数序列
CF1091E New Year and the Acquaintance Estimation
给出一个长为
n 的序列d_1 \sim d_{n} 。求所有可能的d_{n+1} ,使得d_1 \sim d_{n+1} 可以构成无向图的度数序列。
:::::success[题解]
枚举
实际上,定理的成立性关于
如果固定调整方向,就可以用二分求出答案的上下界。
根据定理成立的第一个条件,我们可以得到
| 复杂度 |
|---|
:::::info[代码]
const int N = 5e5 + 5;
int n, a[N], b[N];
i64 s[N];
int check(int x) {
copy(a + 1, a + n + 1, b + 1), b[n + 1] = x;
sort(b + 1, b + n + 2, greater<int>());
for (int i = 1; i <= n + 1; i++) s[i] = s[i - 1] + b[i];
int p = n + 1;
for (int k = 1; k <= n + 1; k++) {
while (p > 0 && b[p] < k) p--;
i64 v = 1LL * k * (k - 1) + 1LL * k * (max(k, p) - k) + s[n + 1] - s[max(k, p)];
if (s[k] > v) return x >= b[k] ? 1 : -1;
} return 0;
}
void _main() {
cin >> n;
for (int i = 1; i <= n; i++) cin >> a[i];
int p = accumulate(a + 1, a + n + 1, 0LL) & 1;
int lo = 0, hi = -1;
for (int l = 0, r = (n - p) / 2; l <= r; ) {
int mid = (l + r) >> 1;
if (check(2 * mid + p) >= 0) lo = mid, r = mid - 1;
else l = mid + 1;
}
for (int l = 0, r = (n - p) / 2; l <= r; ) {
int mid = (l + r) >> 1;
if (check(2 * mid + p) <= 0) hi = mid, l = mid + 1;
else r = mid - 1;
}
if (lo > hi) cout << -1;
else for (int i = lo; i <= hi; i++) cout << 2 * i + p << ' ';
}
:::::