返回题解分享
讨论 / 题解分享/ 帖子详情

二叉树的秘密 - 题解

#include <iostream>
#include <vector>
#include <algorithm>
#include <unordered_set>
using namespace std;

const int MAXN = 10005;
vector<int> t[MAXN];  // 存储树的邻接表
int n, x;  // n 为节点数,x 为藏宝节点
int node_count[MAXN];  // 存储每个子树的节点数

// 计算每个子树的节点数
void dfs_count(int node, int parent) 
{
    node_count[node] = 1;  // 计入当前节点
    for (int child : t[node]) 
    {
        if (child != parent) 
        {
            dfs_count(child, node);
            node_count[node] += node_count[child];  // 累加子节点的数量
        }
    }
}

// 按照规则遍历树并计算访问节点数
int dfs_traverse(int node, int parent, int target, unordered_set<int>& visited) 
{
    visited.insert(node);
    int count = 1;

    if (node == target) 
    {
        return count;  // 找到宝藏,返回已访问节点数
    }
    vector<int> children;
    for (int child : t[node]) 
    {
        if (child != parent) 
        {
            children.push_back(child);
        }
    }

    if (children.size() == 2) // 如果有两个子节点
    {  
        // 按照子树节点数来排序
        sort(children.begin(), children.end(), [](int a, int b) {
            return node_count[a] < node_count[b];
        });
    }

    // 遍历子节点
    for (int child : children) 
    {
        if (visited.find(child) == visited.end()) 
        {
            count += dfs_traverse(child, node, target, visited);
            if (visited.find(target) != visited.end()) 
            {
                return count;
            }
        }
    }
    
    visited.erase(node);
    return count;
}

int main() {
    while (cin >> n >> x) 
    {
        // 清空树和节点计数
        for (int i = 1; i <= n; ++i) 
        {
            t[i].clear();
        }
        
        // 读取树的结构
        for (int i = 1; i <= n; ++i) 
        {
            int k;
            cin >> k;
            for (int j = 0; j < k; ++j) 
            {
                int child;
                cin >> child;
                t[i].push_back(child);
            }
        }

        // 计算每个子树的节点数
        dfs_count(1, -1);
        
        // 访问节点并计算访问的总节点数
        unordered_set<int> visited;
        int result = dfs_traverse(1, -1, x, visited);
        cout << result << endl;
    }

    return 0;
}
0 回复 0 转发 0 喜欢 4 阅读
回复 (0)
默认 最新
暂无回复,快来抢沙发!