Hard

题目描述

给你一个由 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 <= 10^5
  • 2 <= edges.length <= 10^5
  • edges[i].length == 2
  • 1 <= ai, bi <= n
  • ai != bi
  • 没有重复的边

提示：

  • 注意我们添加的每条边都会恰好改变两个节点的度数。
  • 原图中度数为奇数的节点数量应该是 0、2 或 4。尝试分别处理这些情况。

解题思路

解题思路

这道题的核心是理解图论中的一个重要性质：每添加一条边会使两个节点的度数各增加1。

关键观察

  1. 要使所有节点度数为偶数，度数为奇数的节点必须变为偶数
  2. 每添加一条边影响两个节点的度数，奇数+1=偶数，偶数+1=奇数
  3. 最多只能添加2条边，因此最多能改变4个节点的度数

分情况讨论

设度数为奇数的节点数为 odd_count：

  1. odd_count = 0: 已经满足条件，返回true
  2. odd_count = 2: 需要连接这两个奇度数节点，检查它们之间是否已有边
  3. odd_count = 4: 需要添加2条边，有3种配对方式，检查是否至少有一种可行
  4. odd_count为其他值: 无法通过添加至多2条边解决

实现要点

  • 使用邻接表存储图结构，便于快速查询两节点间是否有边
  • 统计每个节点的度数，找出所有奇度数节点
  • 根据奇度数节点的数量进行相应的可行性检查

推荐使用set或邻接表来存储图，查询边的存在性时间复杂度为O(1)或O(log n)。

代码实现

class Solution {
public:
    bool isPossible(int n, vector<vector<int>>& edges) {
        vector<set<int>> graph(n + 1);
        vector<int> degree(n + 1, 0);
        
        // 构建图和统计度数
        for (auto& edge : edges) {
            int u = edge[0], v = edge[1];
            graph[u].insert(v);
            graph[v].insert(u);
            degree[u]++;
            degree[v]++;
        }
        
        // 找出度数为奇数的节点
        vector<int> oddNodes;
        for (int i = 1; i <= n; i++) {
            if (degree[i] % 2 == 1) {
                oddNodes.push_back(i);
            }
        }
        
        int oddCount = oddNodes.size();
        
        if (oddCount == 0) return true;
        if (oddCount == 2) {
            // 检查两个奇度数节点是否已连接
            return graph[oddNodes[0]].find(oddNodes[1]) == graph[oddNodes[0]].end();
        }
        if (oddCount == 4) {
            // 尝试三种配对方式
            int a = oddNodes[0], b = oddNodes[1], c = oddNodes[2], d = oddNodes[3];
            return (graph[a].find(b) == graph[a].end() && graph[c].find(d) == graph[c].end()) ||
                   (graph[a].find(c) == graph[a].end() && graph[b].find(d) == graph[b].end()) ||
                   (graph[a].find(d) == graph[a].end() && graph[b].find(c) == graph[b].end());
        }
        
        return false;
    }
};

class Solution:
    def isPossible(self, n: int, edges: List[List[int]]) -> bool:
        graph = [set() for _ in range(n + 1)]
        degree = [0] * (n + 1)
        
        # 构建图和统计度数
        for u, v in edges:
            graph[u].add(v)
            graph[v].add(u)
            degree[u] += 1
            degree[v] += 1
        
        # 找出度数为奇数的节点
        odd_nodes = [i for i in range(1, n + 1) if degree[i] % 2 == 1]
        odd_count = len(odd_nodes)
        
        if odd_count == 0:
            return True
        if odd_count == 2:
            # 检查两个奇度数节点是否已连接
            return odd_nodes[1] not in graph[odd_nodes[0]]
        if odd_count == 4:
            # 尝试三种配对方式
            a, b, c, d = odd_nodes
            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

public class Solution {
    public bool IsPossible(int n, IList<IList<int>> edges) {
        var graph = new HashSet<int>[n + 1];
        var degree = new int[n + 1];
        
        for (int i = 0; i <= n; i++) {
            graph[i] = new HashSet<int>();
        }
        
        // 构建图和统计度数
        foreach (var edge in edges) {
            int u = edge[0], v = edge[1];
            graph[u].Add(v);
            graph[v].Add(u);
            degree[u]++;
            degree[v]++;
        }
        
        // 找出度数为奇数的节点
        var oddNodes = new List<int>();
        for (int i = 1; i <= n; i++) {
            if (degree[i] % 2 == 1) {
                oddNodes.Add(i);
            }
        }
        
        int oddCount = oddNodes.Count;
        
        if (oddCount == 0) return true;
        if (oddCount == 2) {
            // 检查两个奇度数节点是否已连接
            return !graph[oddNodes[0]].Contains(oddNodes[1]);
        }
        if (oddCount == 4) {
            // 尝试三种配对方式
            int a = oddNodes[0], b = oddNodes[1], c = oddNodes[2], d = oddNodes[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;
    }
}

var isPossible = function(n, edges) {
    const degree = new Array(n + 1).fill(0);
    const adjacentSet = new Array(n + 1).fill(null).map(() => new Set());
    
    for (const [u, v] of edges) {
        degree[u]++;
        degree[v]++;
        adjacentSet[u].add(v);
        adjacentSet[v].add(u);
    }
    
    const oddDegreeNodes = [];
    for (let i = 1; i <= n; i++) {
        if (degree[i] % 2 === 1) {
            oddDegreeNodes.push(i);
        }
    }
    
    const isConnected = (u, v) => adjacentSet[u].has(v);
    
    if (oddDegreeNodes.length === 0) {
        return true;
    } else if (oddDegreeNodes.length === 2) {
        const [u, v] = oddDegreeNodes;
        if (!isConnected(u, v)) {
            return true;
        }
        for (let w = 1; w <= n; w++) {
            if (w !== u && w !== v && !isConnected(u, w) && !isConnected(v, w)) {
                return true;
            }
        }
        return false;
    } else if (oddDegreeNodes.length === 4) {
        const [a, b, c, d] = oddDegreeNodes;
        return (!isConnected(a, b) && !isConnected(c, d)) ||
               (!isConnected(a, c) && !isConnected(b, d)) ||
               (!isConnected(a, d) && !isConnected(b, c));
    } else {
        return false;
    }
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值说明
时间复杂度O(E)E为边数，需要遍历所有边构建图和统计度数
空间复杂度O(V + E)V为节点数，需要存储邻接表和度数数组

相关题目