【暑假】[基本数据结构]根据BFS与DFS确定树

UVa10410 Tree Reconstruction

算法：根据BFS构造pos数组以区分关系，在此基础上对DFS序列操作。注：栈中存父结点，栈顶是最优先的父结点。

代码如下：

 1 #include<cstdio>
 2 #include<vector>
 3 #include<stack>
 4 #define FOR(a,b,c) for(int a=(b);a<(c);a++)
 5 using namespace std;
 6 
 7 const int maxn= 1000 + 10;
 8 
 9 int pos[maxn];      //BFS中的位置关系 
10 vector<int> G[maxn];
11 
12 int main(){
13 int n;
14   while(scanf("%d",&n)==1){
15         int x;
16       FOR(i,1,n+1){
17           scanf("%d",&x);
18           pos[x]=i;
19           G[i].clear();     //G_clear
20       }
21       int root;
22       scanf("%d",&root);
23       stack<int> sta; sta.push(root);
24       int v;
25       FOR(i,1,n){
26           scanf("%d",&v);
27           for(;;){
28               int u=sta.top();
29               if(u==root || pos[u]+1<pos[v]){  //u是v的父结点 
30                   sta.push(v);
31                   G[u].push_back(v);
32                   break;            //直到找到父结点 
33               }
34               else  //u和v是兄弟 返回到u的父结点 
35                sta.pop();
36           }
37       }
38       FOR(u,1,n+1){
39           printf("%d:",u);
40           FOR(j,0,G[u].size()) printf(" %d",G[u][j]);
41         printf("
");
42       }
43   }
44   return 0;
45 }