Skip to content

2508. Add Edges to Make Degrees of All Nodes Even

Description

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.

Solutions

Solution 1: Case Analysis

Thinking

At most two new edges may be added, and they cannot duplicate existing ones, while every degree must become even. The handshaking lemma forces an even number of odd-degree vertices; one edge flips two parities, so more than four odd vertices is impossible.

Build adjacency sets and collect odd-degree vertices \(vs\). Size \(0\) is already fine. For two vertices, connect them if they are not adjacent; otherwise look for a third vertex adjacent to neither. For four vertices, try the three perfect matchings and accept if one pairing uses two missing edges.

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

If the length of \(vs\) is \(0\), it means all nodes in the graph \(g\) have even degrees, so we return true.

If the length of \(vs\) is \(2\), it means there are two nodes with odd degrees in the graph \(g\). If we can directly connect these two nodes with an edge, making all nodes in the graph \(g\) have even degrees, we return true. Otherwise, if we can find a third node \(c\) such that we can connect \(a\) and \(c\), and \(b\) and \(c\), making all nodes in the graph \(g\) have even degrees, we return true. Otherwise, we return false.

If the length of \(vs\) is \(4\), we enumerate all possible pairs and check if any combination meets the conditions. If so, we return true; otherwise, we return false.

In other cases, we return false.

The time complexity is \(O(n + m)\), and the space complexity is \(O(n + m)\). Where \(n\) and \(m\) are the number of nodes and edges, respectively.

 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

 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
46
class Solution {
    public boolean isPossible(int n, List<List<Integer>> edges) {
        Set<Integer>[] g = new Set[n + 1];
        Arrays.setAll(g, k -> new HashSet<>());
        for (var e : edges) {
            int a = e.get(0), b = e.get(1);
            g[a].add(b);
            g[b].add(a);
        }
        List<Integer> vs = new ArrayList<>();
        for (int i = 1; i <= n; ++i) {
            if (g[i].size() % 2 == 1) {
                vs.add(i);
            }
        }
        if (vs.size() == 0) {
            return true;
        }
        if (vs.size() == 2) {
            int a = vs.get(0), b = vs.get(1);
            if (!g[a].contains(b)) {
                return true;
            }
            for (int c = 1; c <= n; ++c) {
                if (a != c && b != c && !g[a].contains(c) && !g[c].contains(b)) {
                    return true;
                }
            }
            return false;
        }
        if (vs.size() == 4) {
            int a = vs.get(0), b = vs.get(1), c = vs.get(2), d = vs.get(3);
            if (!g[a].contains(b) && !g[c].contains(d)) {
                return true;
            }
            if (!g[a].contains(c) && !g[b].contains(d)) {
                return true;
            }
            if (!g[a].contains(d) && !g[b].contains(c)) {
                return true;
            }
            return false;
        }
        return false;
    }
}

 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
class Solution {
public:
    bool isPossible(int n, vector<vector<int>>& edges) {
        vector<unordered_set<int>> g(n + 1);
        for (auto& e : edges) {
            int a = e[0], b = e[1];
            g[a].insert(b);
            g[b].insert(a);
        }
        vector<int> vs;
        for (int i = 1; i <= n; ++i) {
            if (g[i].size() % 2) {
                vs.emplace_back(i);
            }
        }
        if (vs.size() == 0) {
            return true;
        }
        if (vs.size() == 2) {
            int a = vs[0], b = vs[1];
            if (!g[a].count(b)) return true;
            for (int c = 1; c <= n; ++c) {
                if (a != b && b != c && !g[a].count(c) && !g[c].count(b)) {
                    return true;
                }
            }
            return false;
        }
        if (vs.size() == 4) {
            int a = vs[0], b = vs[1], c = vs[2], d = vs[3];
            if (!g[a].count(b) && !g[c].count(d)) return true;
            if (!g[a].count(c) && !g[b].count(d)) return true;
            if (!g[a].count(d) && !g[b].count(c)) return true;
            return false;
        }
        return false;
    }
};

 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
46
47
48
func isPossible(n int, edges [][]int) bool {
    g := make([]map[int]bool, n+1)
    for _, e := range edges {
        a, b := e[0], e[1]
        if g[a] == nil {
            g[a] = map[int]bool{}
        }
        if g[b] == nil {
            g[b] = map[int]bool{}
        }
        g[a][b], g[b][a] = true, true
    }
    vs := []int{}
    for i := 1; i <= n; i++ {
        if len(g[i])%2 == 1 {
            vs = append(vs, i)
        }
    }
    if len(vs) == 0 {
        return true
    }
    if len(vs) == 2 {
        a, b := vs[0], vs[1]
        if !g[a][b] {
            return true
        }
        for c := 1; c <= n; c++ {
            if a != c && b != c && !g[a][c] && !g[c][b] {
                return true
            }
        }
        return false
    }
    if len(vs) == 4 {
        a, b, c, d := vs[0], vs[1], vs[2], vs[3]
        if !g[a][b] && !g[c][d] {
            return true
        }
        if !g[a][c] && !g[b][d] {
            return true
        }
        if !g[a][d] && !g[b][c] {
            return true
        }
        return false
    }
    return false
}

Comments