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 <= 10​​​​​​​5
• 0 <= degrees[i] <= n - 1

解法

方法一

Python3JavaC++Go

评论