2508. Add Edges to Make Degrees of All Nodes Even

HardGraphHash Table

Problem Description

The task involves an undirected graph with n nodes, numbered from 1 to n. A 2D array edges is given, where each edges[i] = [a_i, b_i] represents an edge between nodes a_i and b_i. Our goal is to determine if we can add at most two additional edges to this graph to make the degree of each node even. Note that the graph might not be fully connected, meaning there could be multiple disconnected components.

An important aspect of this problem is understanding the degree of a node. The degree of a node is simply the number of edges connected to it. In the context of this problem, we want to achieve an even degree for every node.

Intuition

To arrive at a solution, we should consider a few key observations:

A node with an odd degree needs to be connected to an additional edge to make its degree even.
If there are no nodes with an odd degree, no additional edges are needed, and the answer is true.
If there are exactly two nodes with an odd degree, we have two cases:
- If the two nodes are not connected, we can simply add an edge between them to make their degrees even.
- If the two nodes are connected, we need to check if there exists a third node such that it is not connected to either of the two nodes with an odd degree. If such a node exists, we can add an edge from each odd-degree node to this third node.
If the number of nodes with an odd degree is four, we then examine the connectivity among these four nodes. We need to add edges between two pairs of these nodes without creating any repeated edges. There are a few different ways this could happen, which are checked in the solution.
- If each pair of these four nodes are not connected, two additional edges can be added between these pairs.
- If there is a different configuration where edges can be added without creating a cycle or repeated edges, then it's possible to satisfy the condition.

By working through these cases, we can reach a conclusion using the conditions above.

Learn more about Graph patterns.

Solution Approach

The solution's implementation adheres to a process that scrutinizes the degrees of nodes and their connections. Here's a breakdown of how the solution operates:

Firstly, the algorithm creates a default dictionary g that maps each node to a set of connected nodes. This helps in keeping track of the edges and simplifies checking for the presence or absence of an edge.
It then iterates over the edges list and populates the dictionary, ensuring both a and b are stored in each other's set, in line with the concept of an undirected graph.
The next step is to create a list vs of nodes that have an odd degree. This is how it's determined which nodes are potential candidates for edge addition, since even-degreed nodes don't need to be altered.
Several conditions are then checked:
- If len(vs) is 0, this means all nodes already have an even degree and the function returns True.
- If there are exactly 2 nodes with an odd degree, the algorithm checks if there is currently an edge between them. If not, an edge can be added, making their degrees even. If there is an edge between these two nodes, we need to find a third node that's not connected to either of them, so we could potentially add two edges without creating duplicates.
- If there are exactly 4 nodes with an odd degree, more scrutiny is required. We want to check all combinations of these four nodes to determine if we can add two edges without repeats. The solution checks each combination, verifying the absence of an edge before considering it for addition. The conditions are explicit checks for non-connectivity between specific nodes.
If any of the conditions above don't hold, meaning if we have an odd number of nodes with odd degrees (other than 2 or 4), the function returns False as it isn't possible to make all degrees even with at most 2 edges added.

The data structure used here, a default dictionary of sets, is key to efficiently managing the connections between nodes and their degrees. The algorithm checks conditions reflecting the constraints of the graph, particularly focusing on the number and connection between nodes with odd degrees.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's use a small example to illustrate the solution approach. Suppose we have a graph with 6 nodes and the following edges: edges = [[1, 2], [2, 3], [3, 4]].

First, we construct the default dictionary g from the edges list:

g = {
  1: {2},
  2: {1, 3},
  3: {2, 4},
  4: {3},
  5: {},
  6: {}
}

Nodes 5 and 6 are isolated and have no connections.

Next, we create the list vs of nodes with odd degrees. After counting the edges, we find that nodes 1, 4, 5, and 6 have odd degrees since they each are connected to only one or no nodes (1 and 4 are each connected to one other node, while 5 and 6 are not connected to any nodes).
```
vs = [1, 4, 5, 6]
```
Now we examine the cases:

a. len(vs) is not 0, so some nodes have odd degrees.

b. There are not exactly 2 nodes with odd degrees, so we cannot simply add one edge between two nodes to even out their degrees. We move on to the next case.

c. Since there are 4 nodes with an odd degree, we have to figure out if we can add two edges to even out the degrees. We need to check the connectivity among these four nodes:
- Nodes 1 and 4 are already connected by the path 1 - 2 - 3 - 4, but not directly, so we can add an edge between 1 and 4.
- Nodes 5 and 6 are isolated and not connected to any nodes, including each other, so we can add an edge between 5 and 6.
After adding these edges, our graph looks like:
```
g = {
  1: {2, 4},
  2: {1, 3},
  3: {2, 4},
  4: {1, 3},
  5: {6},
  6: {5}
}
```
After adding these two new edges, we recount the degrees of each node:
- Node 1: 2 edges (even)
- Node 2: 2 edges (even)
- Node 3: 2 edges (even)
- Node 4: 2 edges (even)
- Node 5: 1 edge (even)
- Node 6: 1 edge (even)
All nodes now have an even degree.

The solution checks these cases and concludes that with the addition of at most two edges, in this case, [1, 4] and [5, 6], every node in the graph can achieve an even degree. The algorithm would return True for this example.

Solution Implementation

1from collections import defaultdict
2from typing import List
3
4class Solution:
5    def isPossible(self, n: int, edges: List[List[int]]) -> bool:
6        # Create a graph as an adjacency set representation
7        graph = defaultdict(set)
8      
9        # Build the graph from the list of edges
10        for node1, node2 in edges:
11            graph[node1].add(node2)
12            graph[node2].add(node1)
13      
14        # Find all vertices with an odd degree
15        odd_degree_vertices = [node for node, neighbors in graph.items() if len(neighbors) % 2 == 1]
16      
17        # If there are no vertices with an odd degree, it's possible
18        if len(odd_degree_vertices) == 0:
19            return True
20      
21        # If there are exactly two vertices with an odd degree
22        if len(odd_degree_vertices) == 2:
23            node_a, node_b = odd_degree_vertices
24          
25            # Check if they are not directly connected, it's possible
26            if node_a not in graph[node_b]:
27                return True
28          
29            # Check if there's any other node that isn't a neighbor to both node_a and node_b
30            return any(node_a not in graph[other_node] and other_node not in graph[node_b] for other_node in range(1, n + 1))
31      
32        # If there are exactly four vertices with an odd degree
33        if len(odd_degree_vertices) == 4:
34            node_a, node_b, node_c, node_d = odd_degree_vertices
35          
36            # Check various combinations of non-adjacency between the odd-degree vertices
37            if node_a not in graph[node_b] and node_c not in graph[node_d]:
38                return True
39            if node_a not in graph[node_c] and node_b not in graph[node_d]:
40                return True
41            if node_a not in graph[node_d] and node_b not in graph[node_c]:
42                return True
43          
44            # If none of the above conditions are true, it's not possible
45            return False
46      
47        # In other cases (odd-degree vertices not equal to 0, 2 or 4), it's not possible
48        return False
49

1class Solution {
2    // Method to check if it is possible to draw all edges in such a way that they don't cross over.
3    public boolean isPossible(int n, List<List<Integer>> edges) {
4        // Create an array of sets to represent the adjacency list for the graph
5        Set<Integer>[] graph = new Set[n + 1];
6        Arrays.setAll(graph, k -> new HashSet<>());
7      
8        // Populate the graph with given edges
9        for (List<Integer> edge : edges) {
10            int nodeA = edge.get(0), nodeB = edge.get(1);
11            graph[nodeA].add(nodeB);
12            graph[nodeB].add(nodeA);
13        }
14      
15        // List to keep track of vertices with an odd degree
16        List<Integer> oddDegreeVertices = new ArrayList<>();
17        for (int i = 1; i <= n; ++i) {
18            if (graph[i].size() % 2 == 1) {
19                oddDegreeVertices.add(i);
20            }
21        }
22      
23        // If no vertices have an odd degree, then it’s possible to draw edges without crossing
24        if (oddDegreeVertices.isEmpty()) {
25            return true;
26        }
27      
28        // If there are exactly two vertices with an odd degree...
29        if (oddDegreeVertices.size() == 2) {
30            int vertexA = oddDegreeVertices.get(0), vertexB = oddDegreeVertices.get(1);
31          
32            // … and they are not directly connected, then it’s possible to draw edges without crossing
33            if (!graph[vertexA].contains(vertexB)) {
34                return true;
35            }
36          
37            // Check if there exists a third vertex, that forms a triangle with the two odd degree vertices
38            for (int vertexC = 1; vertexC <= n; ++vertexC) {
39                if (vertexA != vertexC && vertexB != vertexC && 
40                    !graph[vertexA].contains(vertexC) && !graph[vertexC].contains(vertexB)) {
41                    return true;
42                }
43            }
44          
45            // Otherwise, it's not possible to draw edges without crossing
46            return false;
47        }
48      
49        // If there are exactly four vertices with an odd degree...
50        if (oddDegreeVertices.size() == 4) {
51            int vertexA = oddDegreeVertices.get(0), vertexB = oddDegreeVertices.get(1), 
52                vertexC = oddDegreeVertices.get(2), vertexD = oddDegreeVertices.get(3);
53          
54            // Check different combinations of connections between odd degree vertices to form two pairs that can be
55            // connected without the edges crossing.
56            if (!graph[vertexA].contains(vertexB) && !graph[vertexC].contains(vertexD)) {
57                return true;
58            }
59            if (!graph[vertexA].contains(vertexC) && !graph[vertexB].contains(vertexD)) {
60                return true;
61            }
62            if (!graph[vertexA].contains(vertexD) && !graph[vertexB].contains(vertexC)) {
63                return true;
64            }
65          
66            // Otherwise, it's not possible
67            return false;
68        }
69      
70        // If there are more than four vertices with an odd degree, it’s impossible to draw without crossing.
71        return false;
72    }
73}
74

1class Solution {
2public:
3    bool isPossible(int n, vector<vector<int>>& edges) {
4        // Create an adjacency set (unordered_set) for each vertex for efficient edge lookups
5        vector<unordered_set<int>> graph(n + 1);
6      
7        // Populate the adjacency set with the edges
8        for (auto& edge : edges) {
9            int u = edge[0], v = edge[1];
10            graph[u].insert(v);
11            graph[v].insert(u);
12        }
13      
14        // A vector to keep track of vertices with odd degree
15        vector<int> verticesWithOddDegree;
16      
17        // Check every vertex if it has an odd number of edges (odd degree)
18        for (int i = 1; i <= n; ++i) {
19            if (graph[i].size() % 2) {
20                verticesWithOddDegree.push_back(i);
21            }
22        }
23      
24        // If no vertices have odd degree, a valid path or cycle is possible
25        if (verticesWithOddDegree.empty()) {
26            return true;
27        }
28      
29        // If there are exactly two vertices with an odd degree, check if they're directly connected
30        if (verticesWithOddDegree.size() == 2) {
31            int u = verticesWithOddDegree[0], v = verticesWithOddDegree[1];
32          
33            // If there's no direct edge, then a valid path exists
34            if (!graph[u].count(v)) return true;
35          
36            // Otherwise, look for an alternative vertex to form a path
37            for (int w = 1; w <= n; ++w) {
38                if (u != v && v != w && !graph[u].count(w) && !graph[w].count(v)) {
39                    return true;
40                }
41            }
42          
43            // No path found with two odd vertices
44            return false;
45        }
46      
47        // If there are exactly four vertices with an odd degree, check if two pairs are not directly connected
48        if (verticesWithOddDegree.size() == 4) {
49            int a = verticesWithOddDegree[0], b = verticesWithOddDegree[1];
50            int c = verticesWithOddDegree[2], d = verticesWithOddDegree[3];
51          
52            // Check if there are pairs that do not have an edge between them, resulting in two valid paths
53            if (!graph[a].count(b) && !graph[c].count(d)) return true;
54            if (!graph[a].count(c) && !graph[b].count(d)) return true;
55            if (!graph[a].count(d) && !graph[b].count(c)) return true;
56          
57            // No combination of non-connected pairs with four odd vertices
58            return false;
59        }
60      
61        // If the number of vertices with odd degree is not 0, 2 or 4, a valid path or cycle cannot be formed
62        return false;
63    }
64};
65

1// Define the global adjacency graph as an array of sets for efficient edge lookups.
2const adjacencyGraph: Set<number>[] = [];
3
4/**
5 * Function to determine if a valid path exists for the given graph and number of vertices.
6 * @param {number} n - The number of vertices in the graph.
7 * @param {number[][]} edges - The list of edges in the graph.
8 * @returns {boolean} - True if a valid path or cycle can be formed, false otherwise.
9 */
10function isPossible(n: number, edges: number[][]): boolean {
11    // Initialize the adjacency set for each vertex.
12    for (let i = 1; i <= n; i++) {
13        adjacencyGraph[i] = new Set();
14    }
15
16    // Populate the adjacency set with the edges.
17    edges.forEach(edge => {
18        const [u, v] = edge;
19        adjacencyGraph[u].add(v);
20        adjacencyGraph[v].add(u);
21    });
22
23    // Array to keep track of vertices with an odd degree.
24    const verticesWithOddDegree: number[] = [];
25
26    // Check every vertex for an odd number of edges (odd degree).
27    for (let i = 1; i <= n; i++) {
28        if (adjacencyGraph[i].size % 2) {
29            verticesWithOddDegree.push(i);
30        }
31    }
32
33    // No vertices with an odd degree implies a valid path or cycle is possible.
34    if (verticesWithOddDegree.length === 0) {
35        return true;
36    }
37
38    // Exactly two vertices with an odd degree must not be directly connected.
39    if (verticesWithOddDegree.length === 2) {
40        const [u, v] = verticesWithOddDegree;
41
42        if (!adjacencyGraph[u].has(v)) {
43            return true;
44        }
45
46        // Look for an alternative vertex to connect u and v.
47        for (let w = 1; w <= n; w++) {
48            if (u !== w && v !== w && !adjacencyGraph[u].has(w) && !adjacencyGraph[w].has(v)) {
49                return true;
50            }
51        }
52
53        // No path found.
54        return false;
55    }
56
57    // For exactly four vertices with an odd degree, check for non-connected pairs.
58    if (verticesWithOddDegree.length === 4) {
59        const [a, b, c, d] = verticesWithOddDegree;
60
61        if (!adjacencyGraph[a].has(b) && !adjacencyGraph[c].has(d)) return true;
62        if (!adjacencyGraph[a].has(c) && !adjacencyGraph[b].has(d)) return true;
63        if (!adjacencyGraph[a].has(d) && !adjacencyGraph[b].has(c)) return true;
64
65        // No valid pairs found.
66        return false;
67    }
68
69    // If the number of vertices with an odd degree is not 0, 2, or 4, a valid path or cycle cannot be formed.
70    return false;
71}
72

Time and Space Complexity

The given Python code defines a method isPossible that determines if a graph can be transformed into a single path. Here's the breakdown of the time and space complexity:

Time Complexity

Building the graph with a dictionary of sets, where g maps each node to a set of its neighbors. This operation is O(E) where E is the number of edges, because inserting into a set is O(1) and we do this for each edge twice (once for each direction).
Creating vs, a list of nodes with an odd degree. This is O(V) where V is the number of nodes, since we're checking the number of edges for each node.
Checking the length of vs and performing certain set lookups based on this are all bounded by O(V) for the following reasons:
- When len(vs) equals 0 or 2, the operations are O(1) because we're just performing a fixed number of set lookups.
- When len(vs) equals 4, the comparisons are O(1) for similar reasons.

Therefore, the total time complexity is O(E + V), which simplifies to O(E) if we consider that typically in a connected graph E >= V.

Space Complexity

The graph g uses a set for each node, so the space complexity is O(E) since in the worst case, a fully connected graph might have up to O(V^2) edges, but O(E) represents it more succinctly.
The list vs uses O(V) space in the worst case, as it could include all nodes if they all had odd degrees.

Since E is typically larger than or equal to V, overall the space complexity is O(E).

Learn more about how to find time and space complexity quickly using problem constraints.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Question 1 out of 10

How does quick sort divide the problem into subproblems?

Divide the array into two equal halves by index

Divide the array into two based on whether an element is smaller than an arbitrary value

Divide the array into a stray element and the rest of the array

Quick sort does not use divide and conquer

I don’t know