B3630 排队顺序这道题，我前后交了三版代码才把分拿满，说起来有点丢人——第一版我照着输入顺序直接输出了编号，第二版把「身后」当成了「身前」，直到第三版才老老实实去想「谁站在队头」这个事儿。这道题属于典型的看着简单、动手就翻车的类型，题面短得只有两句话，但里面藏着的链式思维，恰恰是后面学链表、学拓扑排序、学图遍历时反复要用的东西。如果你刚摸到数组和循环，它是一道很好上手的手感题；如果你已经刷了几十道，它也是一道值得回头琢磨「有没有更省空间的写法」的小题。下面我把自己从读错题到写出四种解法、再到踩遍坑的全过程摊开讲，你能直接抄的代码、能直接避的坑，我尽量都写清楚。

1. 先把题目读懂：一条链藏在输入里

1.1 题面在说什么：每个数字都是一句「我后面是谁」

这道题（题号 B3630，题名「排队顺序」）的设定大概是这样的：有 n 名同学排成一列，编号从 1 到 n，每个人只知道一件事——自己身后站的是谁。现在把这 n 个人的「身后信息」按编号顺序丢给你，第 i 个数表示编号为 i 的同学身后那位同学的编号，如果这个数是 0，说明这位同学后面已经没人了，他就是队尾。你要做的，就是把这支队伍从队头到队尾完整还原出来。

说明：不同版本的题面在输入细节上可能略有出入（比如是否单独一行、0 还是 -1 表示队尾），我这里按最常见的那一版展开，你拿到题之后最好先自己核对一遍输入格式和结尾标记，这类细节搞错是最冤的丢分方式。

理解这个设定之后你会发现，整支队伍其实是一根单向的链条：A 后面是 B，B 后面是 C，C 后面没人——那队伍就是 A、B、C。输入给你的不是「队伍顺序」，而是一堆「相邻关系」，你要做的是把这些散落的边重新串成一条链。这跟拼图是一个道理，每一块只告诉你「我右边是哪块」，你得先找到最左边那块，才能一块一块拼下去。

1.2 新手最容易误读的地方：输入顺序不等于队伍顺序

我第一次做这题时犯的错，估计也是大多数人第一次会犯的：看到输入给了 n 个数，就以为按顺序输出就完事了。为什么错？因为输入的下标是「人的编号」，而题目要的输出是「队伍中的位置」，这两个顺序完全不是一回事。

举个具体例子你就明白了。假设 n = 4，输入是2 4 0 3。这串数字的意思是：1 号后面是 2 号，2 号后面是 4 号，3 号后面没人，4 号后面是 3 号。真正的队伍是 1 → 2 → 4 → 3，输出应该是1 2 4 3。如果你直接输出1 2 3 4，或者输出2 4 0 3，都是错的。我第一版就是栽在这儿，样例都没过就开始怀疑人生。

所以做题的第一步永远是把输入里的每个数字翻译成人话，逐条念出来：「编号为 i 的人，后面站的是 a[i]」。念一遍你就知道该干什么了。这个习惯在后面做图论题时更要命，一条边到底是「i 到 j」还是「j 到 i」，方向搞反整个算法就废了。

1.3 数据规模决定了你能不能用笨办法

这类排队还原题的 n 通常在 10 万量级，个别版本会拉到 100 万。这个规模意味着什么？意味着你写个双层循环去「每次从头扫描找队头」的 O(n²) 做法，10 万的数据就是 100 亿次操作，一秒内绝对跑不完，直接超时。

我在纸上算过一笔账：假设评测机每秒能做 1 亿次简单运算，10 万规模的平方是 10¹⁰，也就是 100 亿，理论上要 100 秒。哪怕常数再小，也差了两个数量级。而 O(n) 的写法，10 万次操作连一毫秒都用不到。所以这题的正确姿势必须是一次遍历建表、再一次遍历输出，总共两趟，谁都别想多绕一圈。

这也是我后来养成的一个习惯：看到 n 是 10⁵ 起步，先在脑子里过一遍「哪些操作是 O(n)、哪些是 O(n log n)、哪些是 O(n²)」，把平方级的想法直接掐死，省得写完才发现方向错了。

2. 核心思路拆解：队头是唯一的突破口

2.1 为什么「队头」是最先要找到的东西

链条只能从头往后走，这是它的物理性质决定的。输入给你的信息是「我后面是谁」，全都是往后的方向，没有任何人告诉你「我前面是谁」。所以你站在队伍中间任何一个人身上，都没法往回走，只能顺着往下滑。想完整走完整条链，起点必须是那个前面没有人的人，也就是队头。

我用一个生活场景打比方：你手里有一串钥匙，每把钥匙上都贴着一张纸条，写着「下一把钥匙的样子」，但没有任何一把写着「上一把是谁」。你想把所有钥匙串起来，唯一的办法就是先找出那把从来没被别人「预告」过的钥匙——它就是第一把。

具体到这道题，队头的判定条件非常干脆：在所有 a[i] 的值里，从来没有出现过的那个人，就是队头。因为只要有人在你前面，他的 a 值就会等于你的编号，你就会出现在这堆数字里。反过来，从头到尾没被提到过的编号，前面必定空着，他就是队头。队尾同理，a[i] = 0 的那个人就是队尾。

2.2 用标记数组把「没出现过的人」圈出来

思路有了，怎么实现？最直白的做法是开一个布尔数组hasPrev[]，含义是「这个人前面有人吗」。读入的时候，每读到一个 a[i]，只要它不是 0（不是队尾），就把hasPrev[a[i]] = true。全部读完，从 1 到 n 扫一遍，第一个hasPrev[i] == false的就是队头。

这个做法的好处是逻辑极其清楚，不需要任何脑筋急转弯，写出来自己看着都放心。数组大小开 n + 5 就够，多出来的几个位置是给自己留缓冲，防止下标算错的时候直接踩到别人内存上。这个「多开几个」的习惯我从学数组那会儿就养成了，虽然看着土，但确实救过我不少次。

有一点要特别注意：标记的时候必须判断a[i] != 0。因为 0 不是一个真实的人，它只是个「没人了」的暗号，如果你不加判断地把hasPrev[0]设成 true，虽然不会影响结果（你扫的是 1 到 n），但如果后面写成了从 0 开始扫，就容易出幺蛾子。这种「边界值当成真实数据处理」的失误，属于典型的手滑型 bug，很难靠肉眼看出来。

2.3 四种等价写法，从「好懂」到「好省」

标记法不是唯一解。我后来折腾出了四种写法，各有各的适用场景，摆在一起对比一下你就明白该选哪个：

前驱数组法值得多说一句：读入a[i] = j时，顺手写pre[j] = i，读完以后pre[i] == 0的就是队头。这个写法的妙处在于你同时拿到了反向信息，如果题目后来改问「队伍倒过来输出」，你直接拿 pre 数组就能走，不用重写。

总和相减法是我个人最喜欢的一个小花招，原理很简单：队头是所有编号里唯一没在 a 数组中出现过的那个，那么 1 到 n 的总和，减去所有非零 a[i] 的和，剩下的不就是队头吗？一行代码搞定，连数组都不用开。但这里有个坑要提前说：n 到 10 万时，总和能到 5×10⁹，早就超过 32 位整型的范围了，必须用 64 位整数（C++ 里的long long，Python 不用管）。我第一次写这个的时候用的是 int，n 一到 10 万直接溢出成负数，输出个负号，查了半小时才发现是自己挖的坑。

还有一个更骚的异或法：把 1 到 n 全部异或起来，再异或上所有非零的 a[i]，剩下的就是队头。原理跟总和法一致，但好处是不会溢出，因为异或的结果永远在数值范围内。缺点是可读性差，别人看你的代码得反应三秒。这种写法我只在比赛里赶时间时用过，平时写题解还是老老实实用标记法。

3. 手把手实现：从读入到输出

3.1 数组怎么开、下标从哪里开始

数组开法这件事，看起来是小事，实际上是新手翻车的高频区。有几个原则我建议你直接记住：

第一，数据规模往大了开。如果题面说 n ≤ 10⁵，那就开到 10⁵ + 10，多开十个位置的成本几乎为零，但能挡住大量越界问题。如果在本地用大数组，一定要开成全局变量（放在 main 函数外面），因为全局区内存大，函数内部的栈空间小，开个百万元素的数组放栈上很容易直接崩掉，报出来的错还是一句莫名其妙的「运行时错误」，根本看不出是数组开大了。

第二，下标从 1 开始用。这题的编号是 1 到 n，你要是习惯从 0 开始存，那就得在每次读写时做i - 1的偏移，多写一次就多一次错的机会。做这种和「编号」强绑定的题，我一般直接把数组开到 n + 1，用下标 1 对应编号 1，脑子清爽很多。

第三，布尔数组默认是 false。C++ 的全局数组会被自动清零，hasPrev一开始全是 false，正好符合「一开始假设所有人前面都没人」的初始状态，省去手动初始化。但如果你把它定义在函数里，就变成随机值了，这个细节必须注意。

3.2 找队头与沿链遍历的核心循环

整个算法的骨架只有两段，我把它拆开说。

第一段是建表：一边读入一边标记。读第 i 个数 a[i] 时，做三件事——存进 next 数组、判断它是不是 0、如果不是 0 就把hasPrev[a[i]]标成 true。这一趟下来，链表结构和「谁不是队头」的信息全都有了。

第二段是走链：先扫一遍找到队头 head，然后从 head 出发，while (cur != 0)一路打印，每次把 cur 更新成next[cur]，直到走到 0（队尾后面），循环结束。

这个写法的正确性其实依赖两个题面保证：一是整支队伍是一条完整的链，不会分叉也不会断；二是恰好有一个人前面没人。如果数据不合法（比如成环），这个 while 会一直转下去，程序直接卡死。所以我在写的时候习惯加一个计数器保护，走一步加一，一旦超过 n 还没结束就说明数据有问题，立刻 break 出来。这个习惯在做图论题时更重要，因为那里动不动就给你一个环。

3.3 完整代码：C++ 与 Python 双版本

C++ 版本，我按最朴素的写法来，不加任何花活，方便你对照着看逻辑：

#include <cstdio> const int MAXN = 1000005; int nxt[MAXN]; bool hasPrev[MAXN]; int main() { int n; scanf("%d", &n); for (int i = 1; i <= n; ++i) { scanf("%d", &nxt[i]); if (nxt[i] != 0) { hasPrev[nxt[i]] = true; } } int head = 0; for (int i = 1; i <= n; ++i) { if (!hasPrev[i]) { head = i; break; } } int cur = head; bool first = true; int cnt = 0; while (cur != 0 && cnt < n) { if (!first) putchar(' '); printf("%d", cur); first = false; cur = nxt[cur]; ++cnt; } putchar('\n'); return 0; }

几个细节解释一下。first变量是用来控制空格的，第一项前面不加空格，后面的每项前面补一个，最后统一换行。这样写出来的输出格式绝对干净，不会出现「最后一个数字后面多一个空格」这种被评测机判定格式错误的情况。cnt < n是那个防死循环的保护，正常情况下走不到触发条件。

Python 版本要注意读入效率。这题 n 大的时候，用input()一行行读会明显变慢，我一般用sys.stdin.buffer.read()一次性读进来再切分：

import sys def main(): data = list(map(int, sys.stdin.buffer.read().split())) if not data: return n = data[0] a = data[1:1 + n] nxt = [0] * (n + 2) has_prev = [False] * (n + 2) for i in range(1, n + 1): nxt[i] = a[i - 1] if nxt[i] != 0: has_prev[nxt[i]] = True head = 0 for i in range(1, n + 1): if not has_prev[i]: head = i break ans = [] cur = head cnt = 0 while cur != 0 and cnt < n: ans.append(str(cur)) cur = nxt[cur] cnt += 1 sys.stdout.write(' '.join(ans)) main()

Python 这边我把结果先攒到列表里再一次性join输出，这比在循环里不停print快得多。列表append 是 O(1)，join 是 O(n)，加起来一趟过完，10 万的数据量也就几十毫秒。

3.4 自造数据验证：三种边界用例

代码写完别急着交，自己造几组数据跑一跑，能省掉大量无谓的提交次数。我一般固定测三种：

第一种，最小规模。n = 1，输入就是0，也就是只有一个人而且后面没人。输出应该是1。这组数据专治各种下标越界和初始化为空的问题。我第二次交的那个版本就是在这挂的，因为我把队头的搜索写成了从 0 开始，结果扫到 hasPrev[0] 是 false，直接把 0 当队头输出了。

第二种，顺序被打乱的中等规模。比如 n = 5，输入3 5 0 2 4。翻译一遍：1 后是 3，2 后是 5，3 后没人，4 后是 2，5 后是 4。队伍应该是 1 → 3，同时 4 → 2 → 5 → 4？不对，2 后面是 5，5 后面是 4，4 后面是 2，这就成环了，数据本身不合法。所以我换一组：3 5 0 1 2。翻译：1 后 3，2 后 5，3 后没人，4 后 1，5 后 2。队伍是 4 → 1 → 3，还有 5 → 2 独立成链？也不对，这组数据出现了两条链，同样不合法。正确的构造方式是让所有人串成一条，比如2 4 0 5 3：1 后 2，2 后 4，3 后没人，4 后 5，5 后 3，队伍就是 1 2 4 5 3。

提示：自己造数据时，最容易造出来的就是「两条链」或者「带环」的非法数据。造完先自己手动走一遍，确认能串成一条完整的链再拿去测，否则测出来的错误是你自己的数据错了，白折腾。

第三种，极端顺序。比如 n = 5，输入2 3 4 5 0，队伍是 1 2 3 4 5，这是最顺的情况；再来一组0 1 2 3 4，意思是 1 号后面没人，2 号后是 1，3 号后是 2，4 号后是 3，5 号后是 4，队伍是 5 4 3 2 1，完全倒过来。这两组能测出你的遍历方向有没有搞反。

4. 踩坑实录与排查清单

4.1 输出格式的坑：空格和换行

这类「输出一串数字」的题，格式错误比算法错误更常见。评测机对输出的比对是逐字符的，多一个空格、少一个换行，都会被判错，而且报出来的提示往往只是简单的「格式错误」，根本看不出是哪里多了个空格。

我踩过的坑主要有两个。一个是末尾多空格，用printf("%d ", x)一路输出，最后那个数字后面就带了个尾巴。解决办法就是我上面代码里的first标记法，或者干脆先把结果存进数组，最后用join拼起来。另一个是没有输出换行，有些评测机对这个不敏感，有些就卡你，为了稳妥，最后统一补一个putchar('\n')，成本为零。

还有一种更隐蔽的：如果 n 比较小，你可能不小心在数字之间打了两个空格，肉眼根本看不出来。这种问题只能靠把输出重定向到文件里，用编辑器的「显示空白字符」功能去看。我现在的习惯是写完输出部分，先在本地跑一遍样例，把输出粘到文本编辑器里开可见空白，确认一遍再交。

4.2 下标混用和数组越界

下标问题几乎每道题都会遇到，这题尤其容易出。因为题目里的编号是 1 到 n，而很多人习惯数组从 0 开始，于是代码里就出现了a[i - 1]和a[i]混着用的情况，改到后面自己都不知道自己在写啥。

我的处理方式是全程统一：编号是 1 到 n，那数组就开到 n + 1，所有下标都用 1 到 n，一次偏移都不做。只有在 Python 里从data列表切片的时候才需要减一，而且我把这一步单独拎出来写在一行里，注释清楚，避免后面再碰。

数组越界这个更危险，因为它的表现很不稳定。有时候程序正常跑完，有时候直接崩，有时候悄悄改掉了别的变量的值，让你在完全无关的地方看到诡异的错误。最典型的场景是hasPrev[nxt[i]] = true这一句，如果nxt[i]读进来的值比 n 还大（数据有误或者读错了），这一句就越界了。所以数组多开十个位置这个习惯，真不是迷信。

4.3 死循环：数据不合法时怎么办

按题面保证，输入一定是一条合法的链，理论上不会成环。但实际做题时，你可能会因为读错格式、数组没清空、或者上一组数据的残留，导致程序走进一个环里出不来。表现就是程序不输出也不结束，本地跑的时候一直转，交上去就是「运行超时」。

我的应对方法是永远加一个计数器。不管题目保证得多好，走链的循环里我都写cnt < n这个条件，一旦超过 n 步还没走到头，说明要么数据有环，要么我的 next 数组构造错了，两种情况都该立刻停下。配合在本地调试时打印一下走到哪一步断的，问题很快就能定位。

另外一个小技巧：本地测试时，如果怀疑某组数据有问题，可以先把 next 数组完整打印出来，人工核对一遍「每个人后面是谁」有没有对上。这一步看起来很笨，但对于长度只有十几的测试数据，比盯着代码看快多了。

4.4 常见问题速查表

下面这张表是我把自己和身边人踩过的坑整理出来的，做题时对不上结果可以挨个排查：

5. 做完这道题还能顺手练什么

5.1 换个方向：如果题目给的是「前面是谁」

这题最值得做的变形，就是把输入的含义反过来：每个 a[i] 表示的是「编号 i 的同学前面站的是谁」。这时候你手里握着的全是往前的信息，从任何一个人出发都能往回走，但没法往前走。怎么办？

答案很简单：从队尾出发，一路往前收，收完把整个序列倒序输出。队尾的判定条件也变了，变成「从来没在 a 数组里出现过的那个编号」。这个变形我练过几次，看着只是方向反了一下，但如果你不假思索地套原题的代码，就会输出一个完全颠倒的队伍，而且样例可能还过得去（有些样例正好对称），交上去才发现全错。

这个练习的价值在于让你意识到：链是有方向的，方向决定你从哪头切入。这个思维在后面做有向图遍历、做依赖关系分析时天天要用。

5.2 从一条链到一张网：这题其实是拓扑排序的入门特例

如果你学过拓扑排序，回头再看这道题会有种恍然大悟的感觉。拓扑排序处理的是「有依赖关系的任务排序」，每个任务可能有多个前置，而这道题里每个人最多只有一个前置（站在他前面的人）和最多一个后继，是一张退化成链的图。

所以这题的所有操作，在拓扑排序里都有对应：找队头 = 找入度为 0 的点；沿链走 = 按拓扑序输出；标记 hasPrev = 统计入度。你甚至可以把这题的代码直接改写成拓扑排序的骨架，只把「每个点只有一个出边」这个限制去掉，就变成了一个通用的拓扑排序实现。

我建议你在做完这题之后，去找一道真正的拓扑排序题对比着看，你会发现两者的骨架几乎一模一样，差别只在于一个是单后继（数组就够），一个是多后继（需要邻接表）。这种「从一个特例看到一类问题」的跳跃，是刷题效率提升最快的阶段。

5.3 输入输出习惯的沉淀

最后说点题外的，但我觉得比算法本身更值钱。这道题让我彻底改掉了几个坏习惯。

一是读入必须考虑规模。以前我不管三七二十一就用cin，觉得反正有加速。后来在 n 到 10⁶ 的题上吃过亏，才开始分场景：小数据随便写，大数据一律scanf或者read()一次读入。这个判断现在已经是肌肉记忆了。

二是输出必须检查格式。以前我觉得「差不多就行」，直到被格式错误卡了三次，才开始养成「末尾不留空格、结尾必有换行」的固定写法。现在我的输出部分基本是模板化的，先攒结果再统一输出，几乎不会再出格式问题。

三是写完必须自造数据。样例只能证明你理解了题面，证明不了你的代码是对的。最小规模、打乱顺序、极端顺序这三组数据，我现在是雷打不动要跑的，跑完再去提交，通过率明显上来了。

这道题本身难度不高，但把这几个习惯固化下来之后，我后面做中等题的调试时间至少缩短了一半。有时候一道水题的价值不在于它考了什么算法，而在于它逼你把基本功练扎实了。