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 }