3656. 判断是否存在简单图 🔒
题目描述
给定一个整数数组 degrees，其中 degrees[i] 表示第 i 个顶点的期望度数。
你的任务是确定是否存在一个 恰好 具有这些顶点度数的 无向简单 图。
一个 简单 图没有自环或同一对顶点之间的平行边。
如果存在这样的图，返回 true，否则返回 false。
示例 1：
输入：degrees = [3,1,2,2]
输出：true
解释：
一个可能的无向简单图是：
- 边：
(0, 1), (0, 2), (0, 3), (2, 3) - 度数：
deg(0) = 3，deg(1) = 1，deg(2) = 2，deg(3) = 2。
示例 2：
输入：degrees = [1,3,3,1]
输出：false
解释：
degrees[1] = 3和degrees[2] = 3意味着它们必须连接到所有其他顶点。- 这需要
degrees[0]和degrees[3]至少是 2，但它们都等于 1，这违反了需求。 - 因此，答案是
false。
提示：
1 <= n == degrees.length <= 1050 <= degrees[i] <= n - 1
解法
方法一
思考
给定度数序列，判断是否存在简单无向图。Havel–Hakimi 反复将最大度 \(d\) 与其后 \(d\) 个顶点连边，但 \(n\le 10^5\) 时每次排序过慢。
Erdős–Gállai 定理把判定写成若干前缀不等式，再加度数和为偶数。排序后用前缀和在 \(O(n)\) 内验证。
先检查 \(\sum \deg\) 为偶数且每个度数不超过 \(n-1\)，再按定理比较第 \(k\) 大度之和与右边的截断和。
1 | |
1 | |
1 | |
1 | |