DeepSeek LeetCode 2508.添加边使所有节点度数都为偶数 public boolean isPossible(int n, List＜List＜Integer＞＞ edges)

问题分析我们需要判断能否添加至多两条边不能添加重复边不能添加自环使得图中所有节点的度数都为偶数。---思路步骤1. 统计每个节点的当前度数遍历给出的边统计每个节点的度数。2. 找出度数为奇数的节点设奇数度节点的集合为 odd。因为总度数和是偶数所以 odd.size() 一定是偶数。可能的奇数节点数量0, 2, 4。· 如果 size 0已经满足条件返回 true。· 如果 size 4不可能通过至多两条边调整返回 false。3. 分类讨论情况 1size 2设两个奇度节点为 a 和 b。· 如果 a 与 b 之间没有边那么直接加一条边 (a,b) 即可返回 true。· 如果 a 与 b 之间已经有边我们不能重复加。这时需要在 a 和 b 之间引入一个公共节点 cc ≠ a,b添加 (a,c) 和 (b,c)。但要注意(a,c) 和 (b,c) 必须不存在原图中且 c 可以是除 a,b 外的任意节点。如果有这样的 c返回 true否则 false。情况 2size 4设四个奇度节点为 a,b,c,d。我们需要分成两对每对之间加一条边且这条边在原图中不存在。检查三种可能的配对· (a,b) 和 (c,d)· (a,c) 和 (b,d)· (a,d) 和 (b,c)如果其中一种配对的两条边都不在原始边中返回 true否则 false。---实现细节· 用 SetInteger[] 或 HashSet 存储每个节点的邻居方便快速判断边是否存在。· 注意节点编号从 1 到 n。---代码实现javaimport java.util.*;class Solution {public boolean isPossible(int n, ListListInteger edges) {// 记录每个节点的度数int[] degree new int[n 1];// 记录每个节点的邻居集合SetInteger[] graph new Set[n 1];for (int i 1; i n; i) {graph[i] new HashSet();}for (ListInteger edge : edges) {int u edge.get(0);int v edge.get(1);degree[u];degree[v];graph[u].add(v);graph[v].add(u);}// 收集奇度节点ListInteger oddNodes new ArrayList();for (int i 1; i n; i) {if (degree[i] % 2 1) {oddNodes.add(i);}}int m oddNodes.size();if (m 0) return true;if (m 4) return false;if (m 2) {int a oddNodes.get(0);int b oddNodes.get(1);// 如果 a 和 b 之间没有边直接加一条if (!graph[a].contains(b)) {return true;}// 否则找公共节点 cfor (int c 1; c n; c) {if (c ! a c ! b !graph[a].contains(c) !graph[b].contains(c)) {return true;}}return false;}if (m 4) {int a oddNodes.get(0);int b oddNodes.get(1);int c oddNodes.get(2);int d oddNodes.get(3);// 检查三种配对return (checkPair(graph, a, b) checkPair(graph, c, d))|| (checkPair(graph, a, c) checkPair(graph, b, d))|| (checkPair(graph, a, d) checkPair(graph, b, c));}return false;}private boolean checkPair(SetInteger[] graph, int x, int y) {return !graph[x].contains(y);}}