当前位置：首页 > news >正文

UVa 10410 Tree Reconstruction

news 2026/5/4 7:12:28

题目分析

问题描述

本题要求根据给定的BFS\texttt{BFS}BFS（广度优先搜索）和DFS\texttt{DFS}DFS（深度优先搜索）遍历序列，重建一棵树的结构。这棵树有nnn个节点，编号从111到nnn，并且题目特别说明：当父节点扩展子节点时，子节点是按编号升序遍历的。这意味着在BFS\texttt{BFS}BFS和DFS\texttt{DFS}DFS遍历中，同一个父节点的子节点顺序是一致的。

输入输出格式

输入：第一行是节点数nnn(1≤n≤1000)(1 \leq n \leq 1000)(1≤n≤1000)，接下来一行是BFS\texttt{BFS}BFS序列，再接下来一行是DFS\texttt{DFS}DFS序列。
输出：输出nnn行，每行格式为节点: 子节点1 子节点2 ...，子节点按升序排列。

关键观察

BFS\texttt{BFS}BFS序列反映了树的层级结构，根节点是第一个元素。
DFS\texttt{DFS}DFS序列反映了深度优先的访问顺序，可以用于确定父子关系。
由于子节点按升序遍历，在DFS\texttt{DFS}DFS序列中，一个节点的子节点会连续出现，直到遇到该节点的兄弟节点或更高层级的节点。

算法思路

我们可以利用栈来模拟DFS\texttt{DFS}DFS过程，同时借助BFS\texttt{BFS}BFS序列中的位置信息来确定父子关系。具体来说：

用pos数组记录每个节点在BFS\texttt{BFS}BFS序列中的位置（索引从111开始）。
将DFS\texttt{DFS}DFS序列的第一个节点（根节点）压入栈。
遍历DFS\texttt{DFS}DFS序列的剩余节点：
- 不断检查栈顶节点u：
  - 如果u是根节点或者pos[u] + 1 < pos[x]（其中x是当前DFS\texttt{DFS}DFS节点），说明x是u的子节点。
    - 将x加入u的子节点列表
    - 将x压入栈（因为x可能是后续节点的父节点）
    - 结束循环
  - 否则，弹出栈顶（说明u没有更多子节点）

关键条件pos[u] + 1 < pos[x]的解释：

pos[u] + 1表示在BFS\texttt{BFS}BFS中u的下一个位置
如果pos[x]仅比pos[u]大111，则x可能是u的兄弟节点
如果pos[x]大于pos[u] + 1，说明x在BFS\texttt{BFS}BFS中位于u的"后面足够远"，因此x是u的子节点

复杂度分析

时间复杂度：O(nlog⁡n)O(n \log n)O(nlogn)，主要来自最后的子节点排序
空间复杂度：O(n)O(n)O(n)，用于存储栈、位置数组和子节点列表

代码实现

// Tree Reconstruction// UVa ID: 10410// Verdict: Accepted// Submission Date: 2025-10-16// UVa Run Time: 0.000s//// 版权所有（C）2025，邱秋。metaphysis # yeah dot net#include<iostream>#include<vector>#include<stack>#include<algorithm>usingnamespacestd;intmain(){intn;while(cin>>n){vector<int>pos(n+1);// 记录每个节点在BFS中的位置vector<vector<int>>children(n+1);// 存储每个节点的子节点列表// 读取BFS序列并记录位置for(inti=1;i<=n;i++){intx;cin>>x;pos[x]=i;}// 读取DFS序列vector<int>dfs(n);for(inti=0;i<n;i++){cin>>dfs[i];}introot=dfs[0];// DFS第一个节点是根节点stack<int>st;st.push(root);// 处理DFS序列的剩余节点for(inti=1;i<n;i++){intx=dfs[i];// 当前处理的节点while(true){intu=st.top();// 栈顶节点// 关键判断：如果u是根节点，或者x在BFS中的位置足够靠后if(u==root||pos[u]+1<pos[x]){children[u].push_back(x);// x是u的子节点st.push(x);// 将x压入栈，因为它可能是后续节点的父节点break;}else{st.pop();// u没有更多子节点，弹出}}}// 输出结果for(inti=1;i<=n;i++){cout<<i<<":";// 对子节点排序以满足题目要求的升序输出sort(children[i].begin(),children[i].end());for(intchild:children[i]){cout<<" "<<child;}cout<<endl;}}return0;}