leetcode::number_of_ways_to_reconstruct_a_tree::Solution类 参考

#include <leetcode.h>

静态 Public 成员函数
static int	checkWays (vector< vector< int > > &pairs)

详细描述

在文件 leetcode.h 第 1151 行定义.

成员函数说明

checkWays()

int leetcode::number_of_ways_to_reconstruct_a_tree::Solution::checkWays ( vector< vector< int > > &  pairs )

static

在文件 leetcode.cpp 第 2957 行定义.

                                                          {
            unordered_map<int, unordered_set<int>> adj;
            for(auto &p: pairs) {
                adj[p[0]].emplace(p[1]);
                adj[p[1]].emplace(p[0]);
            }
            /* 检测是否存在根节点*/
            int root = -1;
            for(auto &[node, neighbours]: adj) {
                if(neighbours.size() == adj.size() - 1) {
                    root = node;
                    break;
                }
            }
            if(root == -1) {
                return 0;
            }
 
            int res = 1;
            for(auto &[node, neighbours]: adj) {
                if(node == root) {
                    continue;
                }
                const int currDegree = neighbours.size();
                int parent           = -1;
                int parentDegree     = INT_MAX;
 
                /* 根据 degree 的大小找到 node 的父节点 parent */
                for(const auto &neighbour: neighbours) {
                    if(adj[neighbour].size() < parentDegree && adj[neighbour].size() >= currDegree) {
                        parent       = neighbour;
                        parentDegree = adj[neighbour].size();
                    }
                }
                if(parent == -1) {
                    return 0;
                }
 
                /* 检测 neighbours 是否是 adj[parent] 的子集 */
                for(const auto &neighbour: neighbours) {
                    if(neighbour == parent) {
                        continue;
                    }
                    if(static_cast<unsigned int>(adj[parent].contains(neighbour)) == 0U) {
                        return 0;
                    }
                }
                if(parentDegree == currDegree) {
                    res = 2;
                }
            }
            return res;
        }

引用了 acwing::acwing836_408::root.

被这些函数引用 leetcode::number_of_ways_to_reconstruct_a_tree::TEST().

---

该类的文档由以下文件生成:

• leetcode.h
• leetcode.cpp