1719.重构一棵树的方案数

链接：1719.重构一棵树的方案数
难度：Hard
标签：树、图
简介：请你返回 ways。

题解 1 - cpp

• 编辑时间：2022-02-16
• 执行用时：728ms
• 内存消耗：159.7MB
• 编程语言：cpp
• 解法介绍：找到根节点后，遍历所有节点找到其父节点。

class Solution {
   public:
    int checkWays(vector<vector<int>>& pairs) {
        unordered_map<int, unordered_set<int>> m;
        int root = pairs[0][0];
        // 装载pair到map中，同时记录相邻最多的节点
        for (auto& pair : pairs) {
            m[pair[0]].emplace(pair[1]);
            m[pair[1]].emplace(pair[0]);
            if (m[root].size() < m[pair[0]].size()) root = pair[0];
            if (m[root].size() < m[pair[1]].size()) root = pair[1];
        }
        // 如果最多的节点没法覆盖所有其他节点，那就无法生成树
        if (m[root].size() != m.size() - 1) return 0;
        int ans = 1;
        // 遍历所有子节点
        for (auto& [node, list] : m) {
            if (node == root) continue;
            // 寻找当前子节点的最小父节点， 拥有比当前节点更多的相邻数，
            // 且子节点的所有相邻也与父节点相邻
            int degree = list.size(), parent = -1, parent_degree = INT_MAX;
            for (auto& node : list) {
                if (m[node].size() < parent_degree &&
                    m[node].size() >= degree) {
                    parent = node;
                    parent_degree = m[node].size();
                }
            }
            // 找不到父节点就不可能成树
            if (parent == -1) return 0;
            for (auto& node : list) {
                if (node == parent) continue;
                if (!m[parent].count(node)) return 0;
            }
            // 如果连接数相同说明父子可以替换
            if (parent_degree == degree) ans = 2;
        }
        return ans;
    }
};