uva 10410 - Tree Reconstruction(栈)

题目链接：uva 10410 - Tree Reconstruction

题目大意：给定一个树的BFS和DFS，求这棵树。

解题思路：用栈维护即可。对应BFS序列映射出了每个节点和根节点的距离，遍历dfs序列，对当前节点和栈顶节点比较，如果该节点距离根节点更远，则说明该节点为栈顶节点个孩子节点，则记录后将节点放入栈中。否则弹掉栈顶元素继续比较。需要注意一点，即当元素与栈顶元素的距离值大1的时候要视为相等,因为它们属于兄弟节点

#include <cstdio>
#include <cstring>
#include <stack>
#include <vector>
#include <algorithm>

using namespace std;
const int maxn = 1005;

int N, pos[maxn];
vector<int> g[maxn];

int main () {
    while (scanf("%d", &N) == 1) {
        int x;
        for (int i = 1; i <= N; i++) {
            scanf("%d", &x);
            g[i].clear();
            pos[x] = i;
        }

        int root;
        stack<int> sta;
        scanf("%d", &root);
        sta.push(root);

        for (int i = 1; i < N; i++) {
            scanf("%d", &x);

            while (true) {
                int u = sta.top();

                if (u == root || pos[u] + 1 < pos[x]) {
                    g[u].push_back(x);
                    sta.push(x);
                    break;
                } else 
                    sta.pop();
            }
        }

        for (int i = 1; i <= N; i++) {
            printf("%d:", i);
            for (int j = 0; j < g[i].size(); j++)
                printf(" %d", g[i][j]);
            printf("\n");
        }
    }
    return 0;
}