2508. Add Edges to Make Degrees of All Nodes Even LeetCode Solution

In this guide, you will get 2508. Add Edges to Make Degrees of All Nodes Even LeetCode Solution with the best time and space complexity. The solution to Add Edges to Make Degrees of All Nodes Even problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Add Edges to Make Degrees of All Nodes Even solution in C++
Add Edges to Make Degrees of All Nodes Even solution in Java
Add Edges to Make Degrees of All Nodes Even solution in Python
Additional Resources

2508. Add Edges to Make Degrees of All Nodes Even LeetCode Solution image

Problem Statement of Add Edges to Make Degrees of All Nodes Even

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. The graph can be disconnected.
You can add at most two additional edges (possibly none) to this graph so that there are no repeated edges and no self-loops.
Return true if it is possible to make the degree of each node in the graph even, otherwise return false.
The degree of a node is the number of edges connected to it.

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.

Constraints:

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

Complexity Analysis

Time Complexity: O(n + |\texttt{edges}|)
Space Complexity: O(n + |\texttt{edges}|)

2508. Add Edges to Make Degrees of All Nodes Even LeetCode Solution in C++

class Solution {
 public:
  bool isPossible(int n, vector<vector<int>>& edges) {
    vector<unordered_set<int>> graph(n);

    for (const vector<int>& edge : edges) {
      const int u = edge[0] - 1;
      const int v = edge[1] - 1;
      graph[u].insert(v);
      graph[v].insert(u);
    }

    const vector<int> oddNodes = getOddNodes(graph);
    if (oddNodes.empty())
      return true;
    if (oddNodes.size() == 2) {
      const int a = oddNodes[0];
      const int b = oddNodes[1];
      for (int i = 0; i < n; ++i)
        // Can connect i with a and i with b.
        if (!graph[i].contains(a) && !graph[i].contains(b))
          return true;
    }
    if (oddNodes.size() == 4) {
      const int a = oddNodes[0];
      const int b = oddNodes[1];
      const int c = oddNodes[2];
      const int d = oddNodes[3];
      return (!graph[a].contains(b) && !graph[c].contains(d)) ||
             (!graph[a].contains(c) && !graph[b].contains(d)) ||
             (!graph[a].contains(d) && !graph[b].contains(c));
    }
    return false;
  }

 private:
  vector<int> getOddNodes(const vector<unordered_set<int>>& graph) {
    vector<int> oddNodes;
    for (int i = 0; i < graph.size(); ++i)
      if (graph[i].size() % 2 == 1)
        oddNodes.push_back(i);
    return oddNodes;
  }
};
/* code provided by PROGIEZ */

2508. Add Edges to Make Degrees of All Nodes Even LeetCode Solution in Java

class Solution {
  public boolean isPossible(int n, List<List<Integer>> edges) {
    Set<Integer>[] graph = new Set[n];

    for (int i = 0; i < n; ++i)
      graph[i] = new HashSet<>();

    for (List<Integer> edge : edges) {
      final int u = edge.get(0) - 1;
      final int v = edge.get(1) - 1;
      graph[u].add(v);
      graph[v].add(u);
    }

    List<Integer> oddNodes = getOddNodes(graph);
    if (oddNodes.isEmpty())
      return true;
    if (oddNodes.size() == 2) {
      final int a = oddNodes.get(0);
      final int b = oddNodes.get(1);
      for (int i = 0; i < n; ++i)
        // Can connect i with a and i with b.
        if (!graph[i].contains(a) && !graph[i].contains(b))
          return true;
    }
    if (oddNodes.size() == 4) {
      final int a = oddNodes.get(0);
      final int b = oddNodes.get(1);
      final int c = oddNodes.get(2);
      final int d = oddNodes.get(3);
      return (!graph[a].contains(b) && !graph[c].contains(d)) ||
          (!graph[a].contains(c) && !graph[b].contains(d)) ||
          (!graph[a].contains(d) && !graph[b].contains(c));
    }
    return false;
  }

  private List<Integer> getOddNodes(Set<Integer>[] graph) {
    List<Integer> oddNodes = new ArrayList<>();
    for (int i = 0; i < graph.length; ++i)
      if (graph[i].size() % 2 == 1)
        oddNodes.add(i);
    return oddNodes;
  }
}
// code provided by PROGIEZ

2508. Add Edges to Make Degrees of All Nodes Even LeetCode Solution in Python

class Solution:
  def isPossible(self, n: int, edges: list[list[int]]) -> bool:
    graph = [set() for _ in range(n)]

    for u, v in edges:
      graph[u - 1].add(v - 1)
      graph[v - 1].add(u - 1)

    oddNodes = [i for i, neighbor in enumerate(
        graph) if len(neighbor) % 2 == 1]
    if not oddNodes:
      return True
    if len(oddNodes) == 2:
      a, b = oddNodes
      return any(a not in graph[i] and b not in graph[i] for i in range(n))
    if len(oddNodes) == 4:
      a, b, c, d = oddNodes
      return ((b not in graph[a] and d not in graph[c]) or
              (c not in graph[a] and d not in graph[b]) or
              (d not in graph[a] and c not in graph[b]))
    return False
 # code by PROGIEZ