练77.1 队列复原

解题思路

记录每个值的后继next[i]=j，同时标记j有前驱。1～n里唯一没前驱的值是队首，沿next走到0即可恢复整队。

正确性说明

依照上述推导，逐步维护已处理部分的有效状态。每一步都完成当前项的贡献且不改变已确定的次序，结束时输出的状态恰好对应题目要求。

易错点

输入对顺序不一定与队列顺序相同；0只是尾标志。

复杂度

时间O(n)，空间O(n)。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    vector<int> next(n + 1), hasPrev(n + 1);
    for (int k = 0; k < n; k++) {
        int i, j;
        cin >> i >> j;
        next[i] = j;
        if (j)
            hasPrev[j] = 1;
    }
    int head = 1;
    while (hasPrev[head])
        head++;
    for (int x = head; x; x = next[x])
        cout << x << "\n";
    return 0;
}