LeetCode 题解工作台
添加边使所有节点度数都为偶数
给你一个有 n 个节点的 无向 图，节点编号为 1 到 n 。再给你整数 n 和一个二维整数数组 edges ，其中 edges[i] = [a i , b i ] 表示节点 a i 和 b i 之间有一条边。图不一定连通。 你可以给图中添加 至多 两条额外的边（也可以一条边都不添加），使得图中没有…
2
题型
4
代码语言
3
相关题
当前训练重点
困难 · 图
答案摘要
我们先通过 `edges` 构建图 ，然后找出所有度数为奇数的点，记为 。 如果 的长度为 ，说明图 中所有点的度数都是偶数，直接返回 `true` 即可。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 图 题型思路
题目描述
给你一个有 n 个节点的 无向 图，节点编号为 1 到 n 。再给你整数 n 和一个二维整数数组 edges ，其中 edges[i] = [ai, bi] 表示节点 ai 和 bi 之间有一条边。图不一定连通。
你可以给图中添加 至多 两条额外的边（也可以一条边都不添加），使得图中没有重边也没有自环。
如果添加额外的边后，可以使得图中所有点的度数都是偶数，返回 true ，否则返回 false 。
点的度数是连接一个点的边的数目。
示例 1：
输入：n = 5, edges = [[1,2],[2,3],[3,4],[4,2],[1,4],[2,5]] 输出：true 解释：上图展示了添加一条边的合法方案。 最终图中每个节点都连接偶数条边。
示例 2：
输入：n = 4, edges = [[1,2],[3,4]] 输出：true 解释：上图展示了添加两条边的合法方案。
示例 3：
输入：n = 4, edges = [[1,2],[1,3],[1,4]] 输出：false 解释：无法添加至多 2 条边得到一个符合要求的图。
提示：
3 <= n <= 1052 <= edges.length <= 105edges[i].length == 21 <= ai, bi <= nai != bi- 图中不会有重边
解题思路
方法一：分类讨论
我们先通过 edges 构建图 ，然后找出所有度数为奇数的点，记为 。
如果 的长度为 ，说明图 中所有点的度数都是偶数，直接返回 true 即可。
如果 的长度为 ，说明图 中有两个点的度数是奇数。如果我们可以直接用一条边连接这两个点，使得图 中所有点的度数都是偶数，返回 true；否则，如果我们能找到第三个点 ，使得我们能够连接 和 ，以及连接 和 ，使得图 中所有点的度数都是偶数，返回 true；否则，返回 false。
如果 的长度为 ，我们枚举两两组合的所有情况，判断是否存在满足条件的情况，是则返回 true；否则，返回 false。
其它情况，返回 false。
时间复杂度 ，空间复杂度 。其中 和 分别为节点的数量和边的数量。
class Solution:
def isPossible(self, n: int, edges: List[List[int]]) -> bool:
g = defaultdict(set)
for a, b in edges:
g[a].add(b)
g[b].add(a)
vs = [i for i, v in g.items() if len(v) & 1]
if len(vs) == 0:
return True
if len(vs) == 2:
a, b = vs
if a not in g[b]:
return True
return any(a not in g[c] and c not in g[b] for c in range(1, n + 1))
if len(vs) == 4:
a, b, c, d = vs
if a not in g[b] and c not in g[d]:
return True
if a not in g[c] and b not in g[d]:
return True
if a not in g[d] and b not in g[c]:
return True
return False
return False
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | Depends on the final approach |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Candidate correctly identifies odd-degree nodes and suggests edge pairings.
- question_mark
Candidate understands graph connectivity and considers disconnected components in the approach.
- question_mark
Candidate applies efficient checks to determine if the solution can be achieved with at most two edge additions.
常见陷阱
外企场景- error
Misunderstanding the degree requirement and attempting to add more than two edges.
- error
Failing to properly handle disconnected components of the graph.
- error
Overlooking the effect of adding edges to only two nodes, leading to unnecessary complexity.
进阶变体
外企场景- arrow_right_alt
Consider variations where you must add more than two edges or handle different graph structures.
- arrow_right_alt
Test cases with larger graphs, where the solution must be optimized for performance.
- arrow_right_alt
Edge cases where adding no edges is sufficient, requiring careful handling of already even-degree nodes.