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

难度: Hard

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

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

如果添加额外的边后，可以使得图中所有点的度数都是偶数，返回 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 <= 10⁵
2 <= edges.length <= 10⁵
edges[i].length == 2
1 <= a_i, b_i <= n
a_i != b_i
图中不会有重边

Submission

运行时间: 180 ms

内存: 48.0 MB

class Solution:
    def isPossible(self, n: int, edges: List[List[int]]) -> bool:
        m = len(edges)
        count = {}
        for i in range(m):
            u, v = edges[i][0], edges[i][1]
            if u in count:
                count[u] += 1
            else:
                count[u] = 1
            if v in count:
                count[v] += 1
            else:
                count[v] = 1
        odd = []
        for k in count:
            if count[k] == n-1 and count[k] % 2 == 1:
                return False
            elif count[k] % 2 == 1:
                odd.append(k)
        print(odd, count)
        if len(odd) > 4 or len(odd) % 2 == 1:
            return False
        if len(odd) == 0:
            return True
        elif len(odd) == 2:
            if not [odd[0], odd[1]] in edges and not [odd[1], odd[0]] in edges:
                return True
            for i in range(1,n+1):
                if i in odd:
                    continue
                else:
                    if not [odd[0], i] in edges and not [i, odd[0]] in edges and \
                        not [odd[1], i] in edges and not [i, odd[1]] in edges:
                        return True
            return False
        else:
            l = 0
            for i in range(1, 4):
                a = [odd[0], odd[i]]
                b = [odd[j] for j in range(1,4) if odd[j] not in a]
                if not [a[0], a[1]] in edges and not [a[1], a[0]] in edges and \
                    not [b[0], b[1]] in edges and not [b[1], b[0]] in edges:
                    return True
            return False

Explain

这个题解的思路是首先统计每个节点的度数，然后根据度数的奇偶性来判断是否可以通过添加边使得所有节点的度数都变为偶数。具体来说，如果某个节点的度数等于n-1且为奇数，则无法通过添加边使其变为偶数，直接返回False。然后将所有度数为奇数的节点收集起来，如果奇数节点的个数大于4或为奇数，则无法通过添加边使得所有节点的度数都变为偶数，返回False。如果没有奇数节点，则不需要添加边，返回True。如果有两个奇数节点，检查是否可以通过添加一条边使得这两个节点的度数都变为偶数。如果有四个奇数节点，检查是否可以通过添加两条边使得这四个节点的度数都变为偶数。

时间复杂度: O(m+n)

空间复杂度: O(n)

class Solution:
    def isPossible(self, n: int, edges: List[List[int]]) -> bool:
        m = len(edges)
        count = {}
        for i in range(m):
            u, v = edges[i][0], edges[i][1]
            count[u] = count.get(u, 0) + 1
            count[v] = count.get(v, 0) + 1
        odd = []
        for k in count:
            if count[k] == n-1 and count[k] % 2 == 1:
                return False
            elif count[k] % 2 == 1:
                odd.append(k)
        if len(odd) > 4 or len(odd) % 2 == 1:
            return False
        if len(odd) == 0:
            return True
        elif len(odd) == 2:
            if not [odd[0], odd[1]] in edges and not [odd[1], odd[0]] in edges:
                return True
            for i in range(1,n+1):
                if i in odd:
                    continue
                else:
                    if not [odd[0], i] in edges and not [i, odd[0]] in edges and \
                        not [odd[1], i] in edges and not [i, odd[1]] in edges:
                        return True
            return False
        else:
            for i in range(1, 4):
                a = [odd[0], odd[i]]
                b = [odd[j] for j in range(1,4) if odd[j] not in a]
                if not [a[0], a[1]] in edges and not [a[1], a[0]] in edges and \
                    not [b[0], b[1]] in edges and not [b[1], b[0]] in edges:
                    return True
            return False

Explore

在一个有n个节点的图中，若某个节点的度数为n-1且为奇数时，表示该节点与图中其他所有节点都有连接。因为图中共有n个节点，去除自身后，与该节点连接的节点数为n-1，如果n-1是奇数，则n必然是偶数。为了使该节点的度数变为偶数，需要再添加一个边连接该节点，但是已经与所有其他节点连通，无法增加新的边。因此，无法通过添加边使其度数变为偶数，所以返回False。

每添加一条边，会影响两个节点的度数。因此，添加边只能改变两个节点的度数奇偶性。如果奇数节点的总数为奇数，则无论如何添加边，都会剩下至少一个奇数度数的节点，因为每次操作改变的是两个节点的状态。如果奇数节点大于4，虽然可以通过多次添加边改变奇偶性，但处理和确保最终所有节点度数都为偶数的复杂性和可能性会随着奇数节点数量的增加而降低。通常情况下，如果奇数节点数量超过4，要通过多步骤的边添加来平衡度数会变得复杂和不切实际。

尽管直接连接两个奇数度数的节点是解决问题的简单有效方法，但当这两个节点之间已经存在边时，直接连接不会改变它们的度数奇偶性。此外，尝试通过第三个节点连接这两个奇数节点意味着需要找到两个不与这两个奇数节点相连的其他节点，这可能在密集连接的图中不可行。如果大部分节点都已高度连接，找到这样的第三个节点会很困难，限制了这种方法的适用性。

题解中考虑的是一种特定的配对方式，即首先选择一个节点与其他三个中的一个进行配对，然后将剩下的两个节点配对。虽然这种方法可能有效，但存在其他配对可能性，如完全不同的两两配对方案，可能会在某些情况下更有效或简单。未考虑所有可能的配对方式可能导致某些可行的解决方案被忽略。此外，算法的效率和简洁性可能因为需要检查多种配对方式而受到影响，增加了算法的复杂度和运行时间。