📝 题目大意

有 $N$ 个人排成一列。给定数组 $A$，$A_i = -1$ 表示第 $i$ 个人站在队伍最前面，$A_i \neq -1$ 表示第 $i$ 个人站在第 $A_i$ 个人的正后方。保证信息唯一确定整个队列，要求按从前到后的顺序输出所有人的编号。

💡 解题思路

1. 题目分析：每个 $A_i$ 给出了一个"前驱关系"——第 $i$ 个人紧跟在第 $A_i$ 个人之后。由于题目保证存在且仅存在一种合法排列，这些关系构成了一条从队首到队尾的单向链表。$N \leq 3 \times 10^5$，需要 $O(N)$ 解法。

2. 算法推导：

   • 朴素想法：对于每个人，我们需要知道"谁在我后面"。但原数组 $A$ 存储的是"我在谁后面"（即前驱），不方便直接遍历。因此需要反向建表：对于每个 $i$，若 $A_i \neq -1$，则 next[A_i] = i，表示第 $A_i$ 个人后面是第 $i$ 个人。
   • 同时，找到 $A_i = -1$ 的那个人，他就是队首 head。
   • 从 head 出发，沿着 next 数组依次输出 $N$ 个人，即为答案。
   • 这本质上是一次链表构建 + 遍历，与 std.cpp 的逻辑完全一致：先读入 $A$ 数组，遍历 $i$ 时若 $A_i = -1$ 则记录 head = i，否则将 next[A_i] = i；最后从 head 开始循环 $N$ 次输出并更新 cur = next[cur]。

3. 边界与细节：

   • 输入保证恰好有一个 $A_i = -1$，无需额外判断。
   • 编号从 $1$ 开始，因此数组开 $N+1$ 大小，索引 $0$ 不使用。
   • 输出格式：每个编号之间用空格分隔，行末无多余空格，最后输出换行。
   • 当 $N=1$ 时，只有一个人，$A_1 = -1$，head = 1，next[1] = 0（未赋值），循环一次后 cur = 0，但循环只执行 $N=1$ 次，不会访问 next[0]，安全。

⏱️ 复杂度分析

• 时间复杂度：$O(N)$。读入 $N$ 个数并构建 next 数组需要 $O(N)$，遍历输出同样需要 $O(N)$，总复杂度 $O(N)$。
• 空间复杂度：$O(N)$。两个辅助数组 A 和 next 各占 $O(N)$ 空间，无递归。

💻 标准代码 (C++)

#include <iostream>
#include <vector>
using namespace std;
int main() {
    int N;
    cin >> N;
    vector<int> A(N + 1);       // A[i] 表示第 i 个人的前驱信息
    vector<int> next(N + 1, 0); // next[x] 表示站在第 x 个人正后方的人的编号
    int head = -1;               // 队首编号
    for (int i = 1; i <= N; i++) {
        cin >> A[i];
        if (A[i] == -1) {
            head = i;            // 第 i 个人是队首
        } else {
            next[A[i]] = i;      // 第 i 个人站在第 A[i] 个人的正后方
        }
    }
    int cur = head;              // 从队首开始
    for (int i = 0; i < N; i++) {
        cout << cur;
        if (i < N - 1) cout << " "; // 行末无多余空格
        cur = next[cur];             // 移动到下一个人
    }
    cout << endl;
    return 0;
}