#2508
Add Edges to Make Degrees of All Nodes Even
master · 1850 · lc hard +32 · verified · 35.3% accepted · 363 likes · top 13%
Description
Given an undirected graph with n nodes (1-indexed) and an edge list edges (the graph may be disconnected), determine whether you can add at most two edges — without creating duplicate edges or self-loops — so that every node ends up with an even degree. Return true if possible, otherwise false.
Example 1:
Input: n = 5, edges = [[1,2],[2,3],[3,4],[4,2],[1,4],[2,5]]
Output: true
Explanation: The above diagram shows a valid way of adding an edge.
Every node in the resulting graph is connected to an even number of edges.
Example 2:
Input: n = 4, edges = [[1,2],[3,4]]
Output: true
Explanation: The above diagram shows a valid way of adding two edges.
Example 3:
Input: n = 4, edges = [[1,2],[1,3],[1,4]]
Output: false
Explanation: It is not possible to obtain a valid graph with adding at most 2 edges.
Code
1
2
3