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 也加入队列。这就像一层一层剥洋葱从外向里剥。等整个队列清空所有能够被剥掉的节点都被标记为非环剩下的节点就是环上节点。下面是这个过程的代码片段vectorint indeg(n 1, 0); for (int i 1; i n; i) indeg[to[i]]; queueint que; for (int i 1; i n; i) { if (indeg[i] 0) que.push(i); } vectorint 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] 1entry[v] entry[u]然后继续入队。这个 BFS 非常自然因为每个树节点只有一个出边它的出边指向更靠近环的那个节点所以它只会被它的父节点在反向图中访问一次不需要额外的 visited 标记只需要用depth[v] -1判断是否已经算过。代码片段vectorvectorint rev(n 1); for (int i 1; i n; i) rev[to[i]].push_back(i); vectorint depth(n 1, -1); vectorint entry(n 1, 0); queueint 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; vectorarrayint, 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 最大 2e52 的 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 不在那条链上那就到不了。下面用一张表格总结答案计算方式条件答案cycle_id[a] ! cycle_id[b]-1b 在环上depth[a] 环上距离(entry[a], b)b 在树上且 a 不在 b 的上行链上-1b 在树上且 a 在 b 的上行链上depth[a] - depth[b]这个表格基本就是查询代码的骨架。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] 4pos[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 在左边子树深度为 2b 在右边子树深度为 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; vectorint to(n 1); for (int i 1; i n; i) cin to[i]; // 1. 拓扑排序找环 vectorint indeg(n 1, 0); for (int i 1; i n; i) indeg[to[i]]; queueint que; for (int i 1; i n; i) { if (indeg[i] 0) que.push(i); } vectorint 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. 环编号、环内位置、环长度 vectorint cycle_id(n 1, -1); vectorint pos(n 1, -1); vectorint 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 vectorvectorint rev(n 1); for (int i 1; i n; i) { rev[to[i]].push_back(i); } vectorint depth(n 1, -1); vectorint entry(n 1, 0); queueint 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. 倍增表 vectorarrayint, 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)。如果用vectorarrayint, LOG每个节点 20 个 int2e5 个节点大约是 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 最大 2e52^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循环执行一次就退出环长是 1pos 是 0。查询时如果起点和终点都是这个自环节点答案应该是 0。代码里b在环上时dist (pos[b] - pos[ea] len) % len 0完全正确。二元环也很重要比如 1 - 22 - 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那道题只要倍增表没有环的干扰把倍增跳步练熟之后再来处理这道题的环上距离和树上祖先判断思路会顺很多。画图也很重要随便在纸上画一个环再往环上挂两棵树手动模拟几次查询比直接看代码理解得快得多。