原题链接:
https://leetcode.cn/problems/add-edges-to-make-degrees-of-all-nodes-even/

分类讨论

这题基本上是图论的常规操作，但重要的是分清楚情况。
最多添加两条额外的边使得所有点的度变为偶数
则度为奇数的点数量x(x一定小于4) 有以下几种情况:

  1. x > 4 return false
  2. x = 4 时 a , b ,c ,d这四个点
    存在一对两个点之间不存在边 则可通过加两边方式使得奇数点均变为偶数
    否则不行
  3. x = 2 时 a ,b 两个点
    如果两个点之间 不存在边则直接加边即可
    若两个点之间也存在点 则可通过加两条边的方式 将两个点都向那个点连一条边
    从而达成条件
    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
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    #include<iostream>
    #include<algorithm>
    #include<vector>
    #include<unordered_set>
    using namespace std;
    typedef long long LL;
    class Solution {
    public:
        /*
          这里哈希映射加速的办法还是蛮值得一学的 
          有些极限的情况下stl会比较慢
          本题是两个点 一个10^5 这个数量 故这样*10^6 进行映射则能形成唯一对 
         */
        // 哈希映射 主要用于优化加速
        LL get(int a,int b){
            if(a > b){
                swap(a,b);
            }
            return 1000000ll * a  + b;
        }

        bool isPossible(int n, vector<vector<int>>& edges) {
            unordered_set<LL>s;
            vector<int>d(n + 1,0);
            vector<int>vs;
            for(auto &e : edges){
                int a = e[0];
                int b = e[1];
                s.insert(get(a,b));
                d[a]++;
                d[b]++;   
            }


            // 统计度为奇数的点
            for(int i = 1 ; i <= n ; i++){
                if(d[i] % 2){
                    vs.push_back(i);
                }
            }

            int c = vs.size();

            if(c == 0){
                return true;
            }

            if(c == 2){
                int a = vs[0], b = vs[1];
                if(!s.count(get(a,b))){
                    return true;
                }

                for(int i = 1 ; i <= n ; i++){
                    if(i == a || i == b){
                        continue;
                    }
                    // 如果存在两个点都没有连接边的点 则可以加边
                    if(!s.count(get(a,i)) && !s.count(get(b,i))){
                        return true;
                    }
                }
            }


            if(c == 4){
                vector<int>tmp{vs[0],vs[1],vs[2],vs[3]};
                for(int i = 0 ; i < 24 ; i++){
                    int a = tmp[0],b = tmp[1],c = tmp[2],d = tmp[3];
                    if(!s.count(get(a,b)) && !s.count(get(c,d))){
                        return true;
                    }
                    next_permutation(tmp.begin(),tmp.end());
                }
            }

            return false;
        }
    };