#2508

Hard

LeetCode Problem Workspace

Add Edges to Make Degrees of All Nodes Even

Determine if it's possible to add at most two edges to make all node degrees even in an undirected graph.

Problem Statement

You are given an undirected graph with n nodes numbered from 1 to n and a list of edges. Each edge connects two nodes, and the graph may be disconnected. You are allowed to add at most two edges, ensuring no self-loops or repeated edges. Your task is to determine if it is possible to make the degree of each node in the graph even by adding up to two edges.

The degrees of nodes are critical here, and adding an edge affects the degree of exactly two nodes. This problem involves careful graph analysis and utilizing the effect of edge additions to achieve even node degrees. The solution must determine whether two or fewer edge additions can achieve the required condition for all nodes.

Examples

Example 1

Input: n = 5, edges = [[1,2],[2,3],[3,4],[4,2],[1,4],[2,5]]

Output: true

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

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

It is not possible to obtain a valid graph with adding at most 2 edges.

Constraints

3 <= n <= 105
2 <= edges.length <= 105
edges[i].length == 2
1 <= ai, bi <= n
ai != bi
There are no repeated edges.

Solution Approach

Analyze Node Degrees

Start by calculating the degree of each node. Nodes with odd degrees must be paired with other nodes having odd degrees to form valid edges. Track the odd-degree nodes and assess whether adding two edges can pair all of them.

Check for Pairing Opportunities

Next, determine whether the odd-degree nodes can be paired within the given constraints. If there are more than two odd-degree nodes, return false, as more than two edges would be required. If exactly two odd-degree nodes remain, adding one edge between them is sufficient.

Consider the Graph's Disconnected Components

If the graph is disconnected, check each component individually. The strategy of pairing odd-degree nodes must be applied separately within each component, and the result is only true if all components can satisfy the degree condition with the addition of two or fewer edges.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity depends on the number of nodes and edges. Calculating node degrees and checking pairing possibilities both involve iterating through edges, leading to a time complexity of O(n + m), where n is the number of nodes and m is the number of edges. Space complexity is O(n) due to the storage of node degrees and the odd-degree nodes list.

What Interviewers Usually Probe

Candidate correctly identifies odd-degree nodes and suggests edge pairings.
Candidate understands graph connectivity and considers disconnected components in the approach.
Candidate applies efficient checks to determine if the solution can be achieved with at most two edge additions.

Common Pitfalls or Variants

Common pitfalls

Misunderstanding the degree requirement and attempting to add more than two edges.
Failing to properly handle disconnected components of the graph.
Overlooking the effect of adding edges to only two nodes, leading to unnecessary complexity.

Follow-up variants

Consider variations where you must add more than two edges or handle different graph structures.
Test cases with larger graphs, where the solution must be optimized for performance.
Edge cases where adding no edges is sufficient, requiring careful handling of already even-degree nodes.

FAQ

How can I determine if it's possible to make all node degrees even with two or fewer edges?

You must calculate the degree of each node and ensure that you can pair all odd-degree nodes using two or fewer edge additions.

What happens if there are more than two odd-degree nodes in the graph?

If there are more than two odd-degree nodes, it's impossible to solve the problem with only two edge additions, so the answer is false.

How do disconnected components affect this problem?

Disconnected components must be handled separately, ensuring that each component's odd-degree nodes can be paired with up to two edges.

What is the time complexity for this problem?

The time complexity is O(n + m), where n is the number of nodes and m is the number of edges in the graph.

Can this problem be solved without considering graph connectivity?

No, graph connectivity must be considered, especially when handling disconnected components and pairing odd-degree nodes correctly.

terminal

Solution

Solution 1: Case Analysis

We first build the graph $g$ using `edges`, and then find all nodes with odd degrees, denoted as $vs$.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

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

Continue Practicing

#2421 number of good paths #2374 node with highest edge score #2368 reachable nodes with restrictions