昨天有个学弟在群里问 L2-031 深入虎穴，贴了一段 BFS 代码，样例过了但提交就是有两个点过不去。我让他把起点从 1 号门改成入度为 0 的门，马上 AC。这道题很多人第一眼以为是个普通图论题，甚至想套最短路模板，实际上它就是在一棵有向树里找深度最大的节点，题目里绝大多数信息都在为“树”这个结论做铺垫。今天我用 DFS + 链式前向星把这题完整拆一遍，顺便把入口查找、边数组大小、递归爆栈这几个容易翻车的地方一起说清楚，想打天梯赛或者刚学树的同学都可以直接参考。
1. 题目到底在考什么：从“深入虎穴”里拆出树的模型
1.1 每个节点给出的出口列表，其实就是“孩子列表”
先看输入：第一行是节点数 N，接下来第 i 行给出节点 i 的若干出口。也就是说，节点 i 和这些出口之间有一条“从 i 出发、能走到出口”的有向边。
这里最关键的一个隐藏条件是：整张图只有一个入度为 0 的节点作为入口，并且从入口开始可以到达所有节点。这直接等价于：除入口节点外，其余每个节点的入度都为 1。为什么？因为如果某个非入口节点有两个不同节点能到达它，那从入口出发到它就有两条路径；如果某个非入口节点入度为 0，那它又会变成一个“新入口”，这与唯一入口矛盾。所以整个结构是一棵以入口为根的有向树，每个节点给出的出口就是这棵树的“孩子节点列表”。
很多同学看到“有向图”就条件反射想用 Dijkstra 或者多源 BFS，其实完全不需要。题目要求的无非是：从根节点出发，找一条最长的向下路径，输出这条路径终点的编号。这不就是树的深度问题吗？
1.2 入口怎么找：入度为 0 不是 1 号门
样例里碰巧 1 号门是入口，于是不少人直接dfs(1)，提交后部分测试点通不过。正确做法是读边的时候顺手统计入度：
int indeg[N]; // 读入时： indeg[v]++;全部读完后，从 1 到 N 扫一遍，第一个indeg[i] == 0的就是入口：
int root = 1; for (int i = 1; i <= n; ++i) { if (indeg[i] == 0) { root = i; break; } }这道题保证有唯一入口，所以可以直接 break。如果以后遇到不保证唯一的题目，就不能简单 break 了，得把所有入度为 0 的点都作为起点分别遍历，或者再根据题意特殊处理。
1.3 同深度输出编号最小，更新答案别漏等号
题目还有一个要求：如果有多个节点距离入口一样远，输出编号最小的那个。这导致深度更新的条件不能只写>，还得在深度相等时比较编号：
if (depth > maxDepth || (depth == maxDepth && u < ans)) { maxDepth = depth; ans = u; }这个==的情况特别容易被忽略，而且一旦漏掉，样例往往还是能过的，因为样例的答案可能只有一个，或者恰好编号顺序碰巧正确。等数据里出现并列时，就是白丢的 3 分。我自己的习惯是，只要题面出现“编号最小/最大”“字典序最小”这类关键词，就会在更新答案的函数里单独写一段相等的判断，绝不让它漏掉。
2. 前向星建图：head、to、nxt的配合与边数陷阱
2.1 为什么竞赛里常用链式前向星
很多人会问：明明用vector<int> child[N]存树不是更简单吗？当然可以。不过链式前向星是竞赛里很基础也很常用的建图方式，它能做到用紧凑的数组存储所有边，遍历子节点时通过数组下标跳转，常数小、缓存友好。更重要的是，很多老题目、老 OJ 的编译环境和内存限制比较奇怪，链式前向星在极端环境下会比 vector 更稳。
我不是说 vector 不行，而是建议你至少掌握前向星，这样才能在需要的时候写出更省内存、更可控的代码。尤其是遇到那种 N 到 10 万、递归深度还可能到 10 万的题，vector 本身没问题，但如果你连前向星都不会，那读别人的题解都会困难。
2.2 加边函数的三个数组到底怎么联动
链式前向星的核心是三个数组：head、to、nxt，外加一个边计数tot。
head[u]：节点 u 的第一条出边在to数组里的下标。to[idx]：第 idx 条边指向的节点编号。nxt[idx]：第 idx 条边的“兄弟边”下标，也就是同一个起点的上一条边存在哪。
加边函数写成：
void addEdge(int u, int v) { to[++tot] = v; nxt[tot] = head[u]; head[u] = tot; }用的时候遍历节点 u 的所有出边：
for (int e = head[u]; e; e = nxt[e]) { int v = to[e]; // v 是 u 的一个孩子 }这里用的是头插法，也就是每次都把新边插到链表头部。所以遍历顺序和输入顺序是反的。但对求深度来说，顺序不重要；如果遇到需要按输入顺序遍历的题，可以考虑尾插法或者在 dfs 之前做一次排序，但本题完全不需要。
2.3 边数组只需 N+5：树的总边数是 N-1
前向星的to和nxt数组开多大？这是本题特别容易踩的坑。如果你没有意识到它是树，很容易想：每个节点都可能连到其他 N-1 个节点，那最多有 N*(N-1) 条边，于是写出const int MAXM = 100005 * 100005，不是编译失败就是内存超限。
但一旦确认了“唯一入口 + 每个非根节点入度为 1”，整棵树的边数就是固定的：
除根节点外，每个节点有且只有一条入边，所以总边数 = N - 1。
因此to和nxt开到N + 5就足够。这也是为什么这题的边数组可以用const int MAXN = 100005复用，不需要额外开一个巨大的MAXM。
如果你实在担心题目数据不按套路出牌，也可以把to和nxt声明成vector<int>，动态 push_back。不过以天梯赛的数据习惯，前向星开N+5是绝对安全的。
3. DFS求最深节点：递归版、手写栈与爆栈自救
3.1 递归版DFS：深度参数和答案更新
用递归写 DFS 是最直观的。入口节点深度定为 1（也可以定为 0，只要全程统一就行），每向下走一层深度加 1。进入节点时先更新答案，再遍历所有子节点。
int maxDepth = 0, ans = 1; void dfs(int u, int depth) { if (depth > maxDepth || (depth == maxDepth && u < ans)) { maxDepth = depth; ans = u; } for (int e = head[u]; e; e = nxt[e]) { int v = to[e]; dfs(v, depth + 1); } }这里特别注意：因为是树，路径唯一，不需要vis数组，不会走回头路。我在初学阶段总是习惯性地加一个标记数组，后来发现对这种输入结构，加了反而画蛇添足，还容易出错。树本身就是天然的无环图，递归天然不会重复访问。
3.2 显式栈模拟DFS：不会爆栈的写法
递归最大的隐患是爆栈。当树退化成一条链，比如 1 -> 2 -> 3 -> ... -> N，递归深度最大就到 N。当 N 是 10 万时，在很多 OJ 的默认栈空间下，直接段错误。
我自己就遇到过：本地跑好好的，提交到 OJ 变成运行错误，人都懵了。后来加了一行编译指令才过，但如果当时直接用手写栈，根本不用跟环境折腾。
显式栈写法也简单，用一个栈存(节点编号, 当前深度)的二元组，弹出时更新答案，然后把它所有子节点压入栈：
stack<pair<int, int>> st; st.push({root, 1}); while (!st.empty()) { auto [u, depth] = st.top(); st.pop(); if (depth > maxDepth || (depth == maxDepth && u < ans)) { maxDepth = depth; ans = u; } for (int e = head[u]; e; e = nxt[e]) { st.push({to[e], depth + 1}); } }注意这里压栈顺序不影响答案，因为我们对每个节点都会单独更新一次深度，不会因为先处理哪个孩子而改变最终的最大值。
如果你想让代码更简洁，也可以用 BFS 的队列写法，层数天然等于深度，完全没有递归烦恼。不过既然题目技术点写着 DFS，我还是更推荐掌握手写栈这种“迭代 DFS”的姿势。
3.3 深度初值、N=1和递归边界
有些同学喜欢把maxDepth初始化为INT_MIN，其实没必要。入口节点深度为 1，只要maxDepth初始化为 0，入口节点第一次更新时就能正确覆盖。如果初始化成INT_MIN当然也能过，但没必要增加心理负担。
还要注意 N = 1 的边界：只有一个节点，它自己就是入口，深度为 1，答案就是 1。使用上面的代码，dfs(1, 1)会先把答案设为 1，然后发现没有子节点，结束。输出 1，没问题。
递归边界其实不用刻意写if (depth > ans)之类，因为进入节点就更新，叶子节点更新完没有子边，自然返回。
4. 完整AC代码与测试用例验证
4.1 可直接提交的完整代码
把前面所有内容拼起来，就是一份完整的可提交代码：
#include <bits/stdc++.h> using namespace std; const int MAXN = 100005; int n; int head[MAXN], to[MAXN], nxt[MAXN], tot; int indeg[MAXN]; int maxDepth = 0, ans = 1; void addEdge(int u, int v) { to[++tot] = v; nxt[tot] = head[u]; head[u] = tot; } void dfs(int u, int depth) { if (depth > maxDepth || (depth == maxDepth && u < ans)) { maxDepth = depth; ans = u; } for (int e = head[u]; e; e = nxt[e]) { int v = to[e]; dfs(v, depth + 1); } } int main() { scanf("%d", &n); for (int i = 1; i <= n; ++i) { int k; scanf("%d", &k); while (k--) { int v; scanf("%d", &v); addEdge(i, v); indeg[v]++; } } int root = 1; for (int i = 1; i <= n; ++i) { if (indeg[i] == 0) { root = i; break; } } dfs(root, 1); printf("%d\n", ans); return 0; }如果担心递归爆栈，把dfs(root, 1)换成前面手写栈版本即可，其他部分完全不用动。
4.2 用一个小型图验证代码逻辑
为了不依赖原题样例，我自己构造一个非常小的输入来验证：
6 2 2 3 1 4 1 5 1 6 0 0这个数据的结构是：
- 1 号门通向 2、3
- 2 号门通向 4
- 3 号门通向 5
- 4 号门通向 6
- 5、6 没有出口
入度统计后，只有 1 号门的入度为 0，所以根是 1。DFS 从 1 出发，深度为 1；节点 2、3 深度为 2；节点 4、5 深度为 3；节点 6 深度为 4。最大深度是 4，对应节点 6，代码输出 6。
你可以把这份输入替换进去试，应该一秒出结果。如果输出不是 6，说明入口查找或深度更新哪里出了问题。
4.3 为什么这题不需要visited数组
我前面反复说不需要vis，这里再解释一下为什么。
在一般的有向图里，如果没有访问标记，DFS 可能无限循环。但本题的数据结构是树：每个节点只有一个父亲，从根出发的路径是唯一的，不可能走回已经访问过的节点。所以就算你不开vis，程序也不会死循环。
这也反过来提醒我们：判断一个题能不能用简单的 DFS 求深度，先确认它是不是树（或森林）。如果图中可能有环，那就必须加访问标记，甚至要考虑更复杂的做法。
5. 三个让大佬都翻车的细节与调试建议
5.1 入口找错：样例过了不代表起点正确
这题最阴险的地方是，样例的入口恰好就是 1 号门，于是很多人理所当然把起点写成 1。一旦测试数据里入口不是 1，你从 1 号门出发最多只能遍历 1 号门所在的子树，而真正的入口可能是另一棵子树，这就导致答案完全不对。
我的排查经验是：如果 DFS 输出结果的深度明显偏小，或者总有几个点过不去，第一件事就是检查起点是不是入度为 0 的节点。你可以在调试时打印所有入度为 0 的节点，看看是不是只有一个、是不是你选的根。这比一点点查遍历逻辑要快得多。
5.2 边数组开爆：以为是普通图结果MLE
前向星数组开太大会直接内存超限，开太小会数组越界或段错误。如果你还没有意识到这是树，极可能写出to[MAXN * MAXN]，这种代码连编译都不一定过，更别说提交了。
我的建议是，读题时先把“唯一入口”“从入口可达所有节点”这样的条件圈出来，马上反应出“这是一棵树，边数是 N-1”。这样边数组就敢放心开MAXN + 5。如果你实在不确定，就用vector<int> child[MAXN]，动态扩容，至少不会 MLE，遍历也没问题。
5.3 递归爆栈后的排查思路：段错误不等于数组越界
当你看到一个运行错误，不要只往“数组越界”方向想。如果数组大小开得没问题，那就要考虑递归深度。
N = 10 万、树退化成一条链时，递归调用的深度就是 10 万层。默认递归栈一般不够。我遇到过一次，本地 Visual Studio 能跑，提交到某个 OJ 就崩，排查了半天才发现是系统栈太浅。
解决方式有三种：
- 用显式栈模拟 DFS（推荐，代码不复杂）；
- 用 BFS 队列替代递归；
- 在代码开头加栈扩容指令（不同环境写法不同，不通用）。
我最推荐第二种思路的变种：其实用队列就是按层遍历，天然避开了递归深度问题。但为了训练 DFS 能力，手写栈也值得练一遍。考试时优先选择你最有把握、最不依赖环境的写法。
这题整体难度不大，但入口查找、深度更新、边数组容量、递归深度这几个点组合在一起，足够把基本功不扎实的选手筛掉。我第二次做这道题时就吃了递归爆栈的亏，后来把所有树形 DFS 题都默认用手写栈兜底，再没因为这个原因丢过分。希望这篇题解能帮你把这几个坑一次踩平，下次遇到这类“看似图论、实则树”的题，能直接抓住本质。
