UVa 10410 Tree Reconstruction

题目分析问题描述本题要求根据给定的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//// 版权所有C2025邱秋。metaphysis # yeah dot net#includeiostream#includevector#includestack#includealgorithmusingnamespacestd;intmain(){intn;while(cinn){vectorintpos(n1);// 记录每个节点在BFS中的位置vectorvectorintchildren(n1);// 存储每个节点的子节点列表// 读取BFS序列并记录位置for(inti1;in;i){intx;cinx;pos[x]i;}// 读取DFS序列vectorintdfs(n);for(inti0;in;i){cindfs[i];}introotdfs[0];// DFS第一个节点是根节点stackintst;st.push(root);// 处理DFS序列的剩余节点for(inti1;in;i){intxdfs[i];// 当前处理的节点while(true){intust.top();// 栈顶节点// 关键判断如果u是根节点或者x在BFS中的位置足够靠后if(uroot||pos[u]1pos[x]){children[u].push_back(x);// x是u的子节点st.push(x);// 将x压入栈因为它可能是后续节点的父节点break;}else{st.pop();// u没有更多子节点弹出}}}// 输出结果for(inti1;in;i){couti:;// 对子节点排序以满足题目要求的升序输出sort(children[i].begin(),children[i].end());for(intchild:children[i]){cout child;}coutendl;}}return0;}该算法巧妙地利用了BFS\texttt{BFS}BFS和DFS\texttt{DFS}DFS序列的特性通过栈来维护当前可能的父节点链能够高效地重建树结构。条件pos[u] 1 pos[x]是算法的核心它确保了正确的父子关系判断。