Add edges to make degrees of all nodes even

Hash Table Graph Theory

35.2% acceptance

Feb 25, 2026

363

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.

Solution

Rust

Time O(n)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn is_possible(n: i32, edges: Vec<Vec<i32>>) -> bool {
    use std::collections::HashSet;
    let mut degree = vec![0i32; (n + 1) as usize];
    let mut edge_set: HashSet<(i32, i32)> = HashSet::new();
    for e in &edges {
      let (a, b) = (e[0].min(e[1]), e[0].max(e[1]));
      degree[a as usize] += 1;
      degree[b as usize] += 1;
      edge_set.insert((a, b));
    }
    let odds: Vec<i32> = (1..=n)
      .filter(|&i| degree[i as usize] % 2 == 1)
      .collect();
    let has_edge = |a: i32, b: i32| -> bool {
      let (x, y) = (a.min(b), a.max(b));
      edge_set.contains(&(x, y))
    };
    match odds.len() {
      0 => true,
      2 => {
        let (a, b) = (odds[0], odds[1]);
        if !has_edge(a, b) {
          return true;
        }
        // find c where neither a-c nor b-c is an existing edge
        for c in 1..=n {
          if c != a && c != b && !has_edge(a, c) && !has_edge(b, c) {
            return true;
          }
        }
        false
      }
      4 => {
        let (a, b, c, d) = (odds[0], odds[1], odds[2], odds[3]);
        (!has_edge(a, b) && !has_edge(c, d))
          || (!has_edge(a, c) && !has_edge(b, d))
          || (!has_edge(a, d) && !has_edge(b, c))
      }
      _ => false,
    }
  }
}