HardNo. 2508
Add Edges to Make Degrees of All Nodes Even — LeetCode 2508 Python Solution
- Pattern
- Depth-First Search
- Topics
- Graph, Hash Table
- Reading time
- 4 min
- Source
- leetcode.com
The problem
There is an undirected graph consisting of n nodes numbered from 1 to n. You are given the integer n and a 2D array edges where edges[i] = [ai, bi] indicates that there is an edge between nodes ai and bi.
Example
- 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.
Python solution
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 FalseComplexity
- Time
- O(n + m)
- Space · auxiliary
- O(n + m)
Pattern: Depth-First Search
Follow one path to its end before trying the next — the default way to explore a graph. LeetCode 2508. Add Edges to Make Degrees of All Nodes Even is filed here because LeetCode tags it Graph, which is the vocabulary this hub collects.
The depth-first search guide has the Python template for the pattern and the 366 LeetCode problems that use it.
Related problems
| No. | Problem | Difficulty |
|---|---|---|
| 0133 | Clone Graph | Medium |
| 0924 | Minimize Malware Spread | Hard |
| 0928 | Minimize Malware Spread II | Hard |
| 0947 | Most Stones Removed with Same Row or Column | Medium |
| 0997 | Find the Town Judge | Easy |
| 1311 | Get Watched Videos by Your Friends | Medium |
Frequently asked questions
- How hard is LeetCode 2508. Add Edges to Make Degrees of All Nodes Even?
LeetCode 2508. Add Edges to Make Degrees of All Nodes Even is rated Hard on LeetCode.
- What is the time complexity of LeetCode 2508. Add Edges to Make Degrees of All Nodes Even?
The Python solution on this page runs in O(n + m).
- What is the space complexity of LeetCode 2508. Add Edges to Make Degrees of All Nodes Even?
The Python solution on this page uses O(n + m) auxiliary space.
- What topics does LeetCode 2508. Add Edges to Make Degrees of All Nodes Even cover?
LeetCode 2508. Add Edges to Make Degrees of All Nodes Even is tagged Graph and Hash Table on LeetCode.