企业官网建设流程全解析

CSES 里有一类图论题，表面是科幻故事，内核全是数学结构。Planets Queries II就是典型代表：n 个行星，每个行星有一个传送门指向另一个行星，给你 q 组询问，每组问从 a 传送几次能到 b。我第一次做的时候，以为不就是最短路吗，BFS 一发下去，然后看着 2e5 的 n 和 q 陷入沉思。后来才反应过来，出度全为 1 的图根本不是普通有向图，而是一堆“环上挂着树”的结构，也就是算法竞赛里常说的functional graph。这篇博客就专门拆这道题：从找环、定深度到倍增跳步，把这一类 functional graph 查询问题的套路讲透。适合正在刷 CSES、准备 ICPC，或者单纯想补图论短板的人。

1. 题目速览与问题本质

1.1 题目到底在问什么

题目里给了 n 个行星，编号 1 到 n。每个行星有一个传送门，能且只能传送到一个行星，也就是说每个节点恰好有一条出边，这条出边甚至可以指向自己。查询有两种参数 a 和 b，问的是从 a 出发，沿着传送门走，最少需要多少步能到达 b。如果永远到不了，就输出 -1。

n 和 q 的上限都是 2e5，这意味着暴力做法几乎没有活路。很多人第一反应是“那我对每个询问做一次 BFS”，可惜这是 O(nq) 的复杂度，跑满 2e5 乘 2e5 等于 4e10，严重超时。就算你想到预处理全源最短路，n 个点就要跑 n 次 BFS，同样是 O(n^2)，过不了。

这道题真正想考察的，是利用“每个点出度为 1”这个强约束。因为出度唯一，所以从任何一个点出发，路径都是唯一的，不存在岔路。换句话说，从一个点出发能到达的点集就是一条链，链的尽头一定是一个环。如果目标点在这条链上，那答案就是链上的距离；如果不在，那就是 -1。不存在“绕路更短”的说法，因为根本没有别的路可以绕。

1.2 为什么不能直接 BFS

可以拿现实生活打个比方。普通城市道路是“你说去哪，可能有多条路线”，但 Planets Queries II 里的传送门更像一套单向扶梯系统：你从某一层出发，下一层是唯一确定的，再下一层也是唯一确定的，完全由这一条电梯链决定。你不可能在中途换乘到别的扶梯。

这个特性带来的好处是：任意两点之间的可达性判定变得非常结构化。你不需要搜索整个图，只需要知道“起点最终会进入哪个环，目标点在环上还是在树上，以及起点到目标的相对位置”。这三个信息都能通过预处理在 O(n log n) 时间内得到，查询时每次只花 O(log n)。

理解了这一点，整道题的难度就下降一大半。剩下的工作就是如何高效地提取这些信息。

1.3 结构拆解：环套树（functional graph）

因为每个点只有一条出边，从任意点出发一直走，最终必定会进入一个环。一旦进入环，就永远在这个环上打转，出不去了。不在环上的所有点，会形成若干棵有向树，而且所有树边都指向环的方向，也就是“树根”都是环上的某个点。

可以想象一堆树，树根被绑在一个圆形轨道上，所有树枝都指向轨道。这就是 functional graph 的直观形态：一堆树倒挂在若干有向环上。所以整张图可以拆成两个部分：环上的点，以及环外的树。

这种结构给查询带来了分类依据。如果目标 b 在环上，那只要起点 a 能进入同一个环，就一定能到达 b，只是走多少圈的问题。如果目标 b 在树上，情况更苛刻：起点 a 必须落在“从 b 出发朝树根走”的那条路径上，换句话说，b 必须是 a 路径上的一个节点，否则永远到不了。

2. 三步预处理：找环、定深度、倍增表

2.1 第一步：用拓扑排序把环抠出来

要找环，最直接的方法是 DFS 染色，但在这个特殊图里，拓扑排序更简单，也更不容易错。做法是统计每个节点的入度，然后把所有入度为 0 的节点加进队列。这些节点一定不是环上节点，因为它们没有一个前置节点能走到它们，自然不可能处于一个环中。

接下来模拟删除过程：从队列中取出节点 u，把 u 标记为“非环”，然后找到 u 的唯一后继 v = to[u]，把 v 的入度减 1。如果 v 的入度减到 0，说明所有可能到达 v 的节点都已经被删光了，v 自己也变成了新的“叶子”，于是把 v 也加入队列。

这就像一层一层剥洋葱，从外向里剥。等整个队列清空，所有能够被剥掉的节点都被标记为非环，剩下的节点就是环上节点。下面是这个过程的代码片段：

vector<int> indeg(n + 1, 0); for (int i = 1; i <= n; ++i) indeg[to[i]]++; queue<int> que; for (int i = 1; i <= n; ++i) { if (indeg[i] == 0) que.push(i); } vector<int> is_cycle(n + 1, 1); // 先假设全是环 while (!que.empty()) { int u = que.front(); que.pop(); is_cycle[u] = 0; int v = to[u]; if (--indeg[v] == 0) que.push(v); }

执行完之后，is_cycle[u] == 1的节点就是环上节点。需要注意的是，这个算法修改了indeg数组，后续如果还要用原始入度，记得提前复制一份。

2.2 第二步：从环出发反推深度和入口

找到环之后，下一步是确定每个点离环有多远，以及它最终会进入环上的哪一个点。这里有个很直觉的操作：从所有环上节点同时出发，沿着边的反向方向扩散，也就是走“谁指向我”的关系，这样就能一层一层地走进树的深处。

反向图很容易建：假设原边是 u -> v，那么反向图就是 v 的邻居列表里加入 u。建立rev[v].push_back(u)。

然后先把所有环上节点入队，它们自身到环的距离 depth 是 0，入口 entry 就是自己。之后每次从队列取出 u，遍历rev[u]里的所有邻居 v，如果 v 不是环上节点，就说明 v 是 u 的反向子节点，也就是在树上离环更远一层的点。此时更新depth[v] = depth[u] + 1，entry[v] = entry[u]，然后继续入队。

这个 BFS 非常自然，因为每个树节点只有一个出边，它的出边指向更靠近环的那个节点，所以它只会被它的父节点在反向图中访问一次，不需要额外的 visited 标记，只需要用depth[v] == -1判断是否已经算过。

代码片段：

vector<vector<int>> rev(n + 1); for (int i = 1; i <= n; ++i) rev[to[i]].push_back(i); vector<int> depth(n + 1, -1); vector<int> entry(n + 1, 0); queue<int> bfs; for (int i = 1; i <= n; ++i) { if (is_cycle[i]) { depth[i] = 0; entry[i] = i; bfs.push(i); } } while (!bfs.empty()) { int u = bfs.front(); bfs.pop(); for (int v : rev[u]) { if (is_cycle[v]) continue; if (depth[v] != -1) continue; depth[v] = depth[u] + 1; entry[v] = entry[u]; bfs.push(v); } }

这里有一件重要的事：为什么不能从入度为 0 的叶子开始正向推？因为正向边走的方向是向树根靠近，从叶子出发第一步就走向了它的父节点，但你不知道父节点的深度，所以没法直接算。反过来从环上节点出发向外扩散，每一层深度都是确定的，完美匹配“距离环有几条边”的定义。

2.3 第三步：倍增表预处理

查询时经常需要在同一条链上跳很多步，比如从 a 向上走 depth[a] 步到达环入口。如果一步一步走，单次查询最坏 O(n)，同样不行。标准解法是二进制倍增，也就是预处理好每个点走 2^k 步之后到达的位置。

定义up[x][0] = to[x]，表示从 x 走 1 步到达的点。然后递推：

up[x][k] = up[ up[x][k-1] ][k-1]

含义是先走 2^(k-1) 步到达一个中间点，再从这个中间点继续走 2^(k-1) 步，合起来就是 2^k 步。

预处理完成后，任意跳 steps 步可以把 steps 拆成二进制，比如 steps = 13 = 8 + 4 + 1，那么依次用 up[x][3]、up[x][2]、up[x][0] 跳过去。最多跳 LOG 次，所以单次跳步是 O(log n)。

代码模板：

const int LOG = 20; vector<array<int, LOG>> up(n + 1); for (int i = 1; i <= n; ++i) up[i][0] = to[i]; for (int k = 1; k < LOG; ++k) { for (int i = 1; i <= n; ++i) { up[i][k] = up[ up[i][k - 1] ][k - 1]; } } auto jump = [&](int x, int steps) { for (int k = 0; k < LOG; ++k) { if (steps & (1 << k)) x = up[x][k]; } return x; };

这里 LOG 取 20 是因为 n 最大 2e5，2 的 18 次方是 262144，已经超过 2e5，所以二进制位最多只需要到第 18 位。为了保险起见，用 20 完全足够。如果你把 n 的范围看到更大，那就按ceil(log2(n)) + 1去取。

3. 查询怎么在 O(log n) 内完成

3.1 分类讨论：目标在树上还是在环上

预处理完成之后，查询逻辑就可以统一收口了。每次拿到 a 和 b，先做一层最基础的筛选：判断 a 和 b 是否属于同一个环。这里需要先给每个环编号，并且记录每个环上节点在环内的位置 pos。如果一个在环 A，另一个在环 B，且 A != B，那永远不可能相遇，直接输出 -1。

如果属于同一个环，再看目标 b 的位置。这里有两个分支：

• b 在环上（depth[b] == 0）：那一定能到达，答案是“a 到环的距离 + 在环上从入口走到 b 的距离”。因为一旦 a 进入环，就能沿着环的正向边一直走下去，经过若干步总能到达 b。
• b 在树上（depth[b] > 0）：这时候要求更严格。a 必须正好在 b 的“上行链”上，也就是 b 必须出现在 a 走向环的路径中。如果 a 不在那条链上，那就到不了。

下面用一张表格总结答案计算方式：

这个表格基本就是查询代码的骨架。

3.2 目标在环上的距离计算

如果 b 是环上节点，需要先算出 a 进入环的那个点。这个点就是entry[a]，如果 a 本身就在环上，那 entry[a] 就是 a。由于 depth[a] 表示 a 到环的距离，直接int ea = jump(a, depth[a])就能把 a 跳到环上入口。这一步用得上的正是倍增表。

接下来要算环上从ea走到 b 要多少步。因为每个环都是单向的，所以不是简单的两点之间取绝对值。先预处理每个环上节点在环内的下标pos，下标从 0 开始，并且沿原边方向递增。那么从 ea 到 b 的正向距离就是：

(pos[b] - pos[ea] + len) % len

其中 len 是环的长度。这个公式看起来很基础，但很多人会漏掉“加 len 再取模”这一步。举个实际例子：如果 pos[ea] = 4，pos[b] = 1，环长 len = 5，那么直接1 - 4 = -3，在 C++ 里-3 % 5是 -3，不是 2。加了 len 之后(-3 + 5) % 5 = 2，含义是 ea 要沿着环走 2 步到 b，这跟实际路径图完全吻合。

最终答案就是depth[a] + dist。这里 depth[a] 不为零时，表示 a 要先从树上走到环入口，再在环上走 dist 步。两部分相加就是总步数。

3.3 目标在树上的祖先判断

当 b 在树上时，情况要小心。很多人第一反应是“比较 depth[a] 和 depth[b]，如果 depth[a] 大于等于 depth[b] 就能到”。这个直觉只对了一半，因为深度大只说明 a 离环更远，并不能保证 a 在 b 到环的那条路径上。

举个例子，假设环的根节点 r 下挂着两棵不同的子树，a 在左边子树深度为 2，b 在右边子树深度为 1。depth[a] >= depth[b] 确实满足，但 a 不管怎么走都只会走到左边子树的根，再进入环，根本不可能经过右边子树里的 b。

所以正确做法是：先算diff = depth[a] - depth[b]，如果 diff 是负数，直接排除。否则用jump(a, diff)把 a 向上跳 diff 步，判断跳完之后到达的节点是不是 b。如果正好是 b，说明 b 确实在 a 的上行链上，答案就是 diff；如果不是 b，那说明 a 和 b 在不同分支，答案应该是 -1。

这套判断逻辑非常严谨，也完全符合 functional graph 的“路径唯一”特性。因为路径唯一，所以从 a 向上跳一定步数后到达的节点也是唯一的，拿这个唯一结果和 b 比较，就能得出确定性的结论。

4. 完整 C++ 代码与关键注释

4.1 代码实现

把前面所有步骤串成一份完整可跑的代码。我建议把环编号、环内位置、深度、入口、倍增表这五样东西当成核心预处理数据，查询逻辑只是在这五样东西上做判断。

#include <bits/stdc++.h> using namespace std; const int LOG = 20; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, q; cin >> n >> q; vector<int> to(n + 1); for (int i = 1; i <= n; ++i) cin >> to[i]; // 1. 拓扑排序找环 vector<int> indeg(n + 1, 0); for (int i = 1; i <= n; ++i) indeg[to[i]]++; queue<int> que; for (int i = 1; i <= n; ++i) { if (indeg[i] == 0) que.push(i); } vector<int> is_cycle(n + 1, 1); while (!que.empty()) { int u = que.front(); que.pop(); is_cycle[u] = 0; int v = to[u]; if (--indeg[v] == 0) que.push(v); } // 2. 环编号、环内位置、环长度 vector<int> cycle_id(n + 1, -1); vector<int> pos(n + 1, -1); vector<int> cycle_len(n + 1, 0); int cid = 0; for (int i = 1; i <= n; ++i) { if (is_cycle[i] && cycle_id[i] == -1) { int cur = i; int idx = 0; do { cycle_id[cur] = cid; pos[cur] = idx++; cur = to[cur]; } while (cur != i); cycle_len[cid] = idx; cid++; } } // 3. 反向图 BFS 求 depth 和 entry vector<vector<int>> rev(n + 1); for (int i = 1; i <= n; ++i) { rev[to[i]].push_back(i); } vector<int> depth(n + 1, -1); vector<int> entry(n + 1, 0); queue<int> bfs; for (int i = 1; i <= n; ++i) { if (is_cycle[i]) { depth[i] = 0; entry[i] = i; bfs.push(i); } } while (!bfs.empty()) { int u = bfs.front(); bfs.pop(); for (int v : rev[u]) { if (is_cycle[v]) continue; if (depth[v] != -1) continue; depth[v] = depth[u] + 1; entry[v] = entry[u]; bfs.push(v); } } // 4. 倍增表 vector<array<int, LOG>> up(n + 1); for (int i = 1; i <= n; ++i) { up[i][0] = to[i]; } for (int k = 1; k < LOG; ++k) { for (int i = 1; i <= n; ++i) { up[i][k] = up[ up[i][k - 1] ][k - 1]; } } auto jump = [&](int x, int steps) { for (int k = 0; k < LOG; ++k) { if (steps & (1 << k)) x = up[x][k]; } return x; }; // 5. 处理查询 while (q--) { int a, b; cin >> a >> b; if (cycle_id[a] != cycle_id[b]) { cout << -1 << '\n'; continue; } if (depth[b] > 0) { // b 在树上 if (depth[a] < depth[b]) { cout << -1 << '\n'; } else { int diff = depth[a] - depth[b]; if (jump(a, diff) == b) { cout << diff << '\n'; } else { cout << -1 << '\n'; } } } else { // b 在环上 int ea = jump(a, depth[a]); int len = cycle_len[cycle_id[b]]; int dist = (pos[b] - pos[ea] + len) % len; cout << depth[a] + dist << '\n'; } } return 0; }

这份代码里entry数组在查询时其实没有直接用到，因为jump(a, depth[a])已经能得到入口节点。但我还是保留entry，因为当你调试、对拍、甚至扩展其他题目时，这个信息非常有用。比如 Planets Queries I 这种只问从某个点走 k 步到哪里的题，用不到 entry，但一问“每个点最终进哪个环”，entry 就是现成的答案。

4.2 复杂度分析

预处理部分：拓扑排序 O(n)，反向 BFS O(n)，环编号 O(n)，倍增表 O(n log n)。所以整体预处理是 O(n log n)。

查询部分：每次查询只需要做几次跳转和简单的判断，跳转是 O(log n)。所以总复杂度是 O((n + q) log n)，在 n、q 都是 2e5 时非常轻松。

空间复杂度主要是反向邻接表 O(n)，倍增表 O(n log n)。如果用vector<array<int, LOG>>，每个节点 20 个 int，2e5 个节点大约是 400 万个 int，内存占用 16 MB 左右，完全没有压力。

5. 踩坑记录与常见错误

5.1 拓扑排序删完后 indeg 已经被破坏

拓扑排序会修改indeg数组。如果你在找完环之后还想用入度做别的事情，比如判断树的叶子节点，那就需要提前把原始入度复制一份。不过一般情况下，找环之后入度就没用了，所以不会出问题。真正容易出问题的是把indeg数组和后面反向 BFS 的depth数组搞混，这两个变量名写错很容易导致编译通过了但结果全错。我的建议是命名时区分清楚：indeg、depth、cycle_id，不要用dep和deg这种容易看混的名字。

5.2 为什么 depth 必须从环反向 BFS

我见过有人试图在拓扑排序的同时计算 depth，方法是每删一个节点 u，就令 depth[u] = depth[to[u]] + 1。但这个顺序是有问题的：拓扑排序是从叶子向环的方向删，当你删掉 u 时，to[u]很可能还没有被删，所以它的 depth 还没算出来，你根本加不出来。如果你把删除顺序存下来，然后逆着处理，也就是从靠近环的节点往远处推，倒是可以算，但那样要多存一个数组，还容易理解错。相比之下，从环上节点反向 BFS 是最直观、最不容易出错的做法。

5.3 环上距离公式的取模陷阱

(pos[b] - pos[ea] + len) % len这个公式，最容易漏的是+ len。C++ 对负数取模的结果是负数，如果不加 len，当 pos[b] 小于 pos[ea] 时，你会得到一个负数答案，然后样例都过不了。同时要注意，pos 应该从 0 开始编号。如果你从 1 开始编号，公式会变成(pos[b] - pos[ea] + len) % len，本质一样，但更容易出错。推荐下标从 0 开始，这样环上距离公式完全不需要额外调整。

5.4 倍增 LOG 不够大

LOG 太小是另一个比较隐蔽的错误。n 最大 2e5，2^18 = 262144，也就是说从 2^0 到 2^18 一共 19 个二进制位就足够表示所有小于 2e5 的步数。但如果你习惯性开 LOG = 17，那当步数为 131072 甚至更大时，二进制最高位就超出范围了，跳转结果会不对。稳妥起见，直接用LOG = 20或LOG = 21，或者用while ((1 << LOG) <= n) LOG++动态计算。

5.5 自环和二元环是天然的边界测试

自环是最容易被忽视的边界。如果一个点指向自己，拓扑排序时它的入度永远不会被减到 0，所以会被保留在环上。环编号时do...while循环执行一次就退出，环长是 1，pos 是 0。查询时如果起点和终点都是这个自环节点，答案应该是 0。代码里b在环上时，dist = (pos[b] - pos[ea] + len) % len = 0，完全正确。

二元环也很重要，比如 1 -> 2，2 -> 1。如果从 1 到 1，答案是 0；从 1 到 2，答案是 1；从 2 到 1，答案是 1。这个用例可以快速验证环上距离公式没有把“绕一圈回来”算成 2。

5.6 用随机小图对拍最省心

调试这类图论题，我强烈建议写一个暴力对拍器。随机生成 n 个点，每个点随机选一个目标，然后对若干随机询问跑一遍普通 BFS 作为标准答案，再和优化算法跑出来的答案比对。因为 n 小的时候暴力算法完全可行，跑几百组随机数据就能暴露绝大多数边界错误。这一步在做题时很有价值，因为很多边界情况靠肉眼很难看全，对拍器能在几秒内帮你找出逻辑漏洞。

最后再说一点个人体会

这道题做完之后，我对 functional graph 的处理框架基本就定型了：找环用拓扑排序，算深度/入口用反向 BFS，跳步用倍增。这套组合拳不仅能解决 Planets Queries II，还能迁移到很多类似题，比如查询一个点沿着唯一路径走若干步后的位置、判断两个点是否在同一个环、计算一个点进入环之前走了多少步等等。我个人建议刷这道题之前先做 Planets Queries I，那道题只要倍增表，没有环的干扰，把倍增跳步练熟之后，再来处理这道题的环上距离和树上祖先判断，思路会顺很多。画图也很重要，随便在纸上画一个环，再往环上挂两棵树，手动模拟几次查询，比直接看代码理解得快得多。