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

链接：2508.添加边使所有节点度数都为偶数
难度：Hard
标签：图、哈希表
简介：给你一个有 n  个节点的 无向   图，节点编号为  1  到  n 。再给你整数  n  和一个二维整数数组  edges ，其中  edges[i] = [ai, bi]  表示节点  ai 和  bi  之间有一条边。图不一定连通。如果添加额外的边后，可以使得图中所有点的度数都是偶数，返回 true ，否则返回 false 。

题解 1 - cpp

• 编辑时间：2022-12-18
• 执行用时：512ms
• 内存消耗：186.9MB
• 编程语言：cpp
• 解法介绍：统计所有的可能。

struct Node{
  int val;
 unordered_set<int> next;
};
class Solution {
public:
    bool isPossible(int n, vector<vector<int>>& edges) {
        vector<Node> list(n);
        for (int i = 1; i <= n; i++) list[i - 1].val = i;
        for (auto &edge : edges) {
            int v1 = edge[0] - 1, v2 = edge[1] - 1;
            list[v1].next.insert(v2);
            list[v2].next.insert(v1);
        }
        vector<int> nodes, nodes0;
        for (auto &node : list) {
            if (node.next.size() & 1) {
                // cout << "node.val = " << node.val << ", size = " << node.next.size() << endl;
                if (node.next.size() == n - 1) return false;
                if (node.next.size() == 0) {
                    nodes0.push_back(node.val - 1);
                } else {
                    nodes.push_back(node.val - 1);
                }
            }
        }
        cout << "NODE : " << endl;
        for (auto &node : nodes) {
            cout << list[node].val - 1 << ": ";
            for (auto &next : list[node].next) cout << next << ", ";
            cout << endl;
        }
        if (nodes.size() == 2) return true;
        if (nodes.size() == 0) return true;
        if (nodes.size() > 4) return false;
        if (nodes0.size() > 1) return false;
        if (nodes0.size() == 1) {
            if (nodes.size() == 0) return true;
            if (nodes.size() == 2) return true;
            return false;
        }
        // cout << "===" << endl;
        int ans = false;
        unordered_set<int> used;
        function<void(int,int)> dfs = [&](int i, int line) {
            cout << "i = " << i << ", line = " << line << ", nodes[i] = " << (i == nodes.size() ? -1 : nodes[i]) << endl;
            if (i == nodes.size()) {
                ans = true;
                return;
            }
            if (used.count(nodes[i])) {
                // cout << "1" << endl;
                dfs(i + 1, line);
                return;
            }
            if (line == 0 && i != nodes.size()) return;
                // cout << "2" << endl;
                // cout << "3" << endl;
            Node &node = list[nodes[i]];
            for (int j = i + 1; j < nodes.size(); j++) {
                if (used.count(nodes[j]) || node.next.count(nodes[j])) continue;
                node.next.insert(nodes[j]);
                list[nodes[j]].next.insert(nodes[i]);
                used.insert(nodes[i]);
                used.insert(nodes[j]);
                // cout << "link : " << nodes[i] << ", " << nodes[j] << endl;
                dfs(i + 1, line - 1);
                node.next.erase(nodes[j]);
                list[nodes[j]].next.erase(nodes[i]);
                used.erase(nodes[i]);
                used.erase(nodes[j]);
            }
        };
        dfs(0, 2);
        return ans;
    }
};