UVA10410题：树重建

今天还是一道关于DFS与BFS的题目，但是对于两种搜索挖的有点深，基本上能学到很多关于DFS与BFS的性质。 废话不多说，我们先来看看https://vjudge.net/problem/UVA-10410

我中文大概概括一下，题目给出n个结点并先后给出BFS序和DFS序，然后你需要用这两个序列还原整棵树（如果有多种输出一种即可）。 额，题目意思非常简洁易懂，但是这题想想明白确实没那么容易（花了好久深入思考了BFS和DFS序，以前真没有仔细研究过，好题好题）。

所以我们用邻接表和栈可以过这题。下面贴上代码：

#include <iostream>
#include <vector>
#include <stack>
using namespace std;
const int maxn=1010;

vector<int> G[maxn];
int num[maxn];

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    while(cin>>n){
        int t;
        for(int i=0;i<n;i++){ cin>>t;
            num[t]=i;
            G[i].clear();
        }
        cin>>t;
        int root=t;
        stack<int> s;
        s.push(root);
        for(int i=1;i<n;i++){ cin>>t;
            while(true){
                int u=s.top();
                if(num[u]+1<num[t]||(num[u]+1==num[t]&&u>t)){
                    G[u].push_back(t);
                    s.push(t);
                    break;
                }
                else{
                    s.pop();
                }
            }
        }
        for(int i=1;i<=n;i++){
            cout << i << ':';
            for(int j=0;j<G[i].size();j++){
                cout <<' '<< G[i][j];
            }
            cout << endl;
        }
    }
    return 0;
}

最后今天晚上法国打阿根廷了，虽然不怎么看好这届阿根廷，但