2508-添加边使所有节点度数都为偶数

Raphael Liu Lv10
  2023-09-13 00:47:26 2023-09-13 00:47:26 Created   2023-09-13 16:06:30 2023-09-13 16:06:30 Updated    

给你一个有 n 个节点的 无向 图，节点编号为 1 到 n 。再给你整数 n 和一个二维整数数组 edges ，其中
edges[i] = [ai, bi] 表示节点 ai 和 bi 之间有一条边。图不一定连通。

你可以给图中添加 至多 两条额外的边（也可以一条边都不添加），使得图中没有重边也没有自环。

如果添加额外的边后，可以使得图中所有点的度数都是偶数，返回 true ，否则返回 false 。

点的度数是连接一个点的边的数目。

示例 1：

**输入：** n = 5, edges = [[1,2],[2,3],[3,4],[4,2],[1,4],[2,5]]
**输出：** true
**解释：** 上图展示了添加一条边的合法方案。
最终图中每个节点都连接偶数条边。

示例 2：

**输入：** n = 4, edges = [[1,2],[3,4]]
**输出：** true
**解释：** 上图展示了添加两条边的合法方案。

示例 3：

**输入：** n = 4, edges = [[1,2],[1,3],[1,4]]
**输出：** false
**解释：** 无法添加至多 2 条边得到一个符合要求的图。

提示：

  • 3 <= n <= 105
  • 2 <= edges.length <= 105
  • edges[i].length == 2
  • 1 <= ai, bi <= n
  • ai != bi
  • 图中不会有重边

视频讲解 已出炉，欢迎点赞三连，在评论区分享你对这场周赛的看法~

把度数为奇数的节点记到 odd 中，记 m 为 odd 的长度，分类讨论：

  • 如果 m=0，那么已经符合要求。
  • 如果 m=2，记 x=\textit{odd}[0],y=\textit{odd}[1]：
    • 如果 x 和 y 之间没有边，那么连边之后就符合要求了。
    • 如果 x 和 y 之间有边，那么枚举 [1,n] 的所有不为 x 和 y 的点 i，由于 i 的度数一定是偶数，如果 i 和 x 以及 i 和 y 之间没有边，那么连边之后就符合要求了。
  • 如果 m=4，记 a=\textit{odd}[0],b=\textit{odd}[1],c=\textit{odd}[2],d=\textit{odd}[3]：
    • 如果 a 和 b 以及 c 和 d 之间没有边，那么连边之后就符合要求了。
    • 如果 a 和 c 以及 b 和 d 之间没有边，那么连边之后就符合要求了。
    • 如果 a 和 d 以及 b 和 c 之间没有边，那么连边之后就符合要求了。
  • 其余情况无法满足要求。
[sol1-Python3]
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:
        g = defaultdict(set)
        for x, y in edges:
            g[x].add(y)
            g[y].add(x)
        odd = [i for i, nb in g.items() if len(nb) % 2]
        m = len(odd)
        if m == 0: return True
        if m == 2:
            x, y = odd
            return x not in g[y] or any(
                i != x and i != y and x not in g[i] and y not in g[i]
                for i in range(1, n + 1))
        if m == 4:
            a, b, c, d = odd
            return b not in g[a] and d not in g[c] or \
                   c not in g[a] and d not in g[b] or \
                   d not in g[a] and c not in g[b]
        return False
[sol1-Java]
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
class Solution {
    public boolean isPossible(int n, List<List<Integer>> edges) {
        var g = new Set[n + 1];
        Arrays.setAll(g, e -> new HashSet<Integer>());
        for (var e : edges) {
            int x = e.get(0), y = e.get(1);
            g[x].add(y);
            g[y].add(x);
        }
        var odd = new ArrayList<Integer>();
        for (var i = 1; i <= n; ++i)
            if (g[i].size() % 2 > 0) odd.add(i);
        var m = odd.size();
        if (m == 0) return true;
        if (m == 2) {
            int x = odd.get(0), y = odd.get(1);
            if (!g[x].contains(y)) return true;
            for (var i = 1; i <= n; ++i)
                if (i != x && i != y && !g[i].contains(x) && !g[i].contains(y))
                    return true;
            return false;
        }
        if (m == 4) {
            int a = odd.get(0), b = odd.get(1), c = odd.get(2), d = odd.get(3);
            return !g[a].contains(b) && !g[c].contains(d) ||
                    !g[a].contains(c) && !g[b].contains(d) ||
                    !g[a].contains(d) && !g[b].contains(c);
        }
        return false;
    }
}
[sol1-C++]
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
class Solution {
public:
    bool isPossible(int n, vector<vector<int>> &edges) {
        unordered_set<int> g[n + 1];
        for (auto &e : edges) {
            int x = e[0], y = e[1];
            g[x].insert(y);
            g[y].insert(x);
        }
        vector<int> odd;
        for (int i = 1; i <= n; ++i)
            if (g[i].size() % 2) odd.push_back(i);
        int m = odd.size();
        if (m == 0) return true;
        if (m == 2) {
            int x = odd[0], y = odd[1];
            if (!g[x].count(y)) return true;
            for (int i = 1; i <= n; ++i)
                if (i != x && i != y && !g[i].count(x) && !g[i].count(y))
                    return true;
            return false;
        }
        if (m == 4) {
            int a = odd[0], b = odd[1], c = odd[2], d = odd[3];
            return !g[a].count(b) && !g[c].count(d) ||
                   !g[a].count(c) && !g[b].count(d) ||
                   !g[a].count(d) && !g[b].count(c);
        }
        return false;
    }
};
[sol1-Go]
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
func isPossible(n int, edges [][]int) bool {
	g := map[int]map[int]bool{}
	for _, e := range edges {
		x, y := e[0], e[1]
		if g[x] == nil {
			g[x] = map[int]bool{}
		}
		g[x][y] = true
		if g[y] == nil {
			g[y] = map[int]bool{}
		}
		g[y][x] = true
	}
	odd := []int{}
	for i, nb := range g {
		if len(nb)%2 > 0 {
			odd = append(odd, i)
		}
	}
	m := len(odd)
	if m == 0 {
		return true
	}
	if m == 2 {
		x, y := odd[0], odd[1]
		if !g[x][y] {
			return true
		}
		for i := 1; i <= n; i++ {
			if i != x && i != y && !g[i][x] && !g[i][y] {
				return true
			}
		}
		return false
	}
	if m == 4 {
		a, b, c, d := odd[0], odd[1], odd[2], odd[3]
		return !g[a][b] && !g[c][d] || !g[a][c] && !g[b][d] || !g[a][d] && !g[b][c]
	}
	return false
}

复杂度分析

  • 时间复杂度：O(n+m)，其中 m 为 edges 的长度。
  • 空间复杂度：O(n+m)。
 Comments
On this page
2508-添加边使所有节点度数都为偶数