UVa 10410树重建

https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1351

题意:给出bfs和dfs序列,输出每个结点的子节点。

遍历dfs序列,如果当前访问元素为v,它的前面的元素为u,那么在bfs序列中,如果u后面的那个元素不为v的话,那么v肯定是u的子序列,如果为1的话,则v是u的兄弟结点。

 1 #include<iostream>
 2 #include<vector>
 3 #include<stack>
 4 using namespace std;
 5 
 6 vector<int> treechild[1005];
 7 stack<int> sta;
 8 int order[1005];
 9 
10 int main()
11 {
12     int n, x, i;
13     while (cin >> n && n)
14     {
15         for (i = 1; i <= n; i++)
16         {
17             cin >> x;
18             order[x] = i;
19             treechild[i].clear();
20         }
21         int root;
22         cin >> root;
23         sta.push(root);
24         for (i = 1; i < n; i++)
25         {
26             cin >> x;
27             for (;;)
28             {
29                 int v = sta.top();
30                 if (v == root || order[v] + 1 < order[x])
31                 {
32                     treechild[v].push_back(x);
33                     sta.push(x);
34                     break;
35                 }
36                 else
37                     sta.pop();
38             }
39         }
40         for (i = 1; i <= n; i++)
41         {
42             vector<int>::iterator it = treechild[i].begin();
43             cout << i << ":";
44             for (; it != treechild[i].end(); it++)
45             {
46                 cout << " " << *it;
47             }
48             cout << endl;
49         }
50     }
51     return 0;
52 }        
原文地址:https://www.cnblogs.com/zyb993963526/p/6236723.html