Skip to content

2508. Add Edges to Make Degrees of All Nodes Even 👍

  • Time: $O(n + |\texttt{edges}|)$
  • Space: $O(n + |\texttt{edges}|)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
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].count(a) && !graph[i].count(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].count(b) && !graph[c].count(d)) ||
             (!graph[a].count(c) && !graph[b].count(d)) ||
             (!graph[a].count(d) && !graph[b].count(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() & 1)
        oddNodes.push_back(i);
    return oddNodes;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
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;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
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) & 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