Uber OA 面试真题解析：判断能否通过最多添加两条边让图中所有节点度数为偶数

Given an undirected graph graph that is represented by its adjacency matrix, return whether or not it is possible to add no more than two edges to this graph in order to make the degrees of nodes even.

Keep in mind that in the resulting graph there should be at most one edge between any pair of nodes.

Example:

graph = [[false, true, false, false],
         [true, false, true, false],
         [false, true, false, true],
         [false, false, true, false]]

The output should be solution(graph) = true.

这道题的核心是统计无向图中“奇度数”节点的个数，并判断能否通过最多添加两条不存在的边，把这些奇数度节点全部配对消掉。由于一条新边会让两个端点的度数各加 1，所以奇度数节点数量只能是 0、2 或 4 时才有可能成功：0 个时已经满足要求；2 个时可以尝试直接连这两个点，或者找一个同时与它们都不相连的中间点分两步补边；4 个时则需要枚举三种两两配对方式，只要其中一种配对对应的两条边都不存在即可。题目通常用邻接矩阵表示图，因此实现时先统计每个节点的度数，再根据奇数节点数量做分类判断即可，时间复杂度主要来自枚举节点，适合面试中的贪心与图论基础题。