LeetCode 1059. 从起点到终点的所有路径

2022-03-30 HGNULB 约 11 分钟

文章信息 7 个分类 4 个标签

分类

题目描述

✅ 1059. 从起点到终点的所有路径

题意分析

给定一张 n 个节点的有向图、一个起点 source 和一个终点 destination，要判断是否满足三个条件：从起点出发的每一条路径最终都能走到终点、走到终点后就再也走不动了（终点出度为 0）、并且从起点出发的路径条数是有限的。三条同时成立才返回 true。

标题里的「所有路径」很容易被误读成要枚举路径并返回，其实题目问的是一个全称判断：不存在任何一条从起点出发却没能停在终点的走法。这类全称命题的反面往往更好判定——只要能找出一条反例路径，答案就是 false。反例只有两种形态：走着走着卡在了一个出度为 0 且不是终点的节点上，或者走进了一个环里永远绕不出来。第三个条件「路径条数有限」其实等价于「从起点可达的部分不含环」，因为一旦有环就能绕任意多圈，路径条数立刻变成无限。

约束里的信号很明确：节点数最多一万、边数最多一万，允许 $O(n + m)$ 的一次遍历，但不允许真的去枚举所有路径——即使无环，路径条数也可能随节点数指数增长。图可能有重边、可能不连通，起点也可能等于终点。

边界方面要留意：起点若本身出度为 0，则唯一的「路径」就是原地不动，此时答案取决于起点是不是终点；终点若有出边，那么走到终点还能继续走出去，直接违反第二个条件。

解法：DFS + 访问状态

核心思路

直接枚举所有路径的做法立刻就死在指数爆炸上：哪怕是一张无环图，从起点到终点的路径条数也可能达到 $2^{n}$ 量级，逐条检查根本跑不完。瓶颈在于它把「所有路径都合法」拆成了一条条独立验证，忽略了这些路径之间共享了大量的后缀。

关键观察是把判定沿着节点递归下去：定义「节点 u 是安全的」为「从 u 出发的每一条路径都终止于 destination」。这个性质有一个漂亮的递归结构——若 u 没有出边，则 u 安全当且仅当 u 就是 destination；若 u 有出边，则 u 安全当且仅当它的每一个后继都安全。这样一来，答案就是「source 是否安全」，而每个节点的安全性只需要计算一次，共享后缀带来的重复被彻底消除。

剩下的问题是环。递归到一半可能又转回自己，必须能识别出来。这里用经典的三色标记：状态 0 表示尚未访问，状态 1 表示正在当前递归路径上（灰色），状态 2 表示已经确认安全（黑色）。这就是整个算法的不变量——只要递归过程中遇到一个状态为 1 的节点，说明沿着当前这条路走回了祖先，环被找到，整条路径永远到不了终点，直接判 false；遇到状态为 2 的节点则说明它的安全性早已论证过，可以立即复用结论。

注意这里不存在「已确认不安全」的第三种终态，因为一旦发现某个节点不安全，整个函数会立刻一路返回 false，不会再有别的分支需要查询它，所以两个非零状态就足够了。

解题步骤

第一步，把边列表转成邻接表。原始的 edges 是一堆二元组，按它逐次查找某个节点的后继需要扫描全部边，转成邻接表后可以 $O(1)$ 拿到出边集合，这是所有图论遍历的标准前置步骤。Java 版本要先为 n 个节点各建一个空列表再灌边，Go 版本用 make([][]int, n) 拿到 n 个 nil 切片后直接 append 即可。

第二步，开一个长度为 n 的 state 数组，全部初始化为 0。用整型数组而不是两个布尔数组，是为了让三种状态在一个变量里表达，也让「正在路径上」和「已确认安全」这两层含义不会互相覆盖。

第三步，从 source 发起递归，返回值直接就是答案。递归函数的语义要钉死：dfs(u) 返回「从 u 出发的所有路径是否都终止于 destination」。

第四步，在递归入口先处理非零状态：state[node] != 0 时返回 state[node] == 2。这一句同时干了两件事——状态为 2 说明结论已知且为安全，直接复用，这是记忆化，避免重复展开子图；状态为 1 说明当前节点还在递归栈上就又被访问到了，形成环，返回 false。把两种情况合并成一行是因为它们的返回值恰好可以用同一个比较表达出来。

第五步，处理出度为 0 的节点：graph.get(node).isEmpty() 时返回 node == dest。这是唯一的正向终止条件——走不动了的地方必须正好是终点。这一步必须写在染色之前，因为叶子节点不会进入任何环，没必要标记灰色。

第六步，把当前节点染成灰色 state[node] = 1，表示它已进入当前递归路径。染色时机必须在遍历后继之前，否则环回来时看到的还是 0，检测不出来。

第七步，遍历所有后继递归判断，只要有一个后继返回 false 就立刻返回 false。这里用的是「全称条件」的短路求值：一条坏路径就足以否定全局，不需要看完剩下的分支。注意提前返回时并没有把 state[node] 复位成 0，这不会出问题，因为返回 false 会沿调用链一路传播到最外层，后续不会再有查询发生。

第八步，所有后继都安全时把当前节点染成黑色 state[node] = 2 并返回 true。染黑意味着结论已经确定且不再变化，之后任何路径再走到它都可以直接复用，这正是把指数级路径枚举压成线性遍历的关键。

以 n = 4、edges = [[0,1],[0,2],[1,3],[2,3]]、source = 0、destination = 3 走一遍：邻接表为 0 -> [1, 2]、1 -> [3]、2 -> [3]、3 -> []。调用 dfs(0)，状态为 0 且有出边，染灰 state[0] = 1，先递归 dfs(1)；节点 1 状态为 0 且有出边，染灰后递归 dfs(3)；节点 3 出度为 0，判断 3 == 3 成立返回 true（注意它没有被染色，下次访问会重新走一遍这个 $O(1)$ 判断）；于是节点 1 的所有后继都安全，染黑 state[1] = 2 返回 true。回到节点 0 继续递归 dfs(2)，同样路径染灰、访问节点 3 返回 true、染黑 state[2] = 2 返回 true。节点 0 的两个后继都安全，染黑并返回 true，最终答案为 true。再看一个带环的例子 n = 4、edges = [[0,1],[0,3],[1,2],[2,1]]、source = 0、destination = 3：dfs(0) 染灰后先进 dfs(1)，节点 1 染灰后进 dfs(2)，节点 2 染灰后进 dfs(1)——此时 state[1] 为 1，命中环检测，返回 1 == 2 即 false；这个 false 逐层向上传播，节点 2、节点 1、节点 0 依次立即返回 false，节点 0 的另一条通往终点 3 的好路径根本没被访问，因为一条坏路径已经足以否定全局，最终答案为 false。

代码实现

class Solution {
    // 对每个节点记录状态：0 未访问，1 正在访问，2 已确认安全。
    public boolean leadsToDestination(int n, int[][] edges, int source, int destination) {
        List<List<Integer>> graph = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            graph.add(new ArrayList<>());
        }
        for (int[] e : edges) {
            graph.get(e[0]).add(e[1]);
        }

        int[] state = new int[n];
        return dfs(source, destination, graph, state);
    }

    private boolean dfs(int node, int dest, List<List<Integer>> graph, int[] state) {
        if (state[node] != 0) {
            return state[node] == 2;
        }

        if (graph.get(node).isEmpty()) {
            return node == dest;
        }

        state[node] = 1;

        for (int next : graph.get(node)) {
            if (!dfs(next, dest, graph, state)) {
                return false;
            }
        }

        state[node] = 2;
        return true;
    }
}

func leadsToDestination(n int, edges [][]int, source int, destination int) bool {
    // 对每个节点记录状态：0 未访问，1 正在访问，2 已确认安全。
    graph := make([][]int, n)
    for _, e := range edges {
        graph[e[0]] = append(graph[e[0]], e[1])
    }

    state := make([]int, n)

    var dfs func(int) bool
    dfs = func(node int) bool {
        if state[node] != 0 {
            return state[node] == 2
        }
        if len(graph[node]) == 0 {
            return node == destination
        }

        state[node] = 1
        for _, next := range graph[node] {
            if !dfs(next) {
                return false
            }
        }
        state[node] = 2
        return true
    }

    return dfs(source)
}

复杂度分析

时间复杂度：$O(n + m)$，其中 n 为节点数、m 为边数。建邻接表遍历一次全部边；递归中每个节点最多被真正展开一次（展开后即被染成 1 或直接返回），展开时枚举它的全部出边，因此所有节点的出边总共只被扫描一遍。

空间复杂度：$O(n + m)$。邻接表存下全部边占 $O(m)$，状态数组占 $O(n)$，递归栈深度不超过最长简单路径的长度也就是 $O(n)$，三者相加即为总量。

关键点总结

全称判断要转成「找反例」：与其证明每条路径都好，不如去找唯一一条坏路径，反例只有「卡在非终点的死路」和「陷入环」两种形态，问题立刻具体化，这是处理「所有…都…」型题目的通用起手式。

三色标记是有向图判环的标准工具：灰色代表「在当前递归栈上」，黑色代表「已彻底处理完」，只有回边指向灰色节点才算环，若只用一个布尔 visited，会把「访问过的旁支」误判成环。

把递归函数的语义写成一句可验证的话：「从 u 出发的所有路径是否都终止于 destination」，有了这句话，终止条件、记忆化复用、返回值的含义才能自洽，也才能向面试官论证正确性。

记忆化让指数级的路径枚举退化成线性遍历：路径数可能指数爆炸，但节点数是线性的，把结论挂在节点上而不是路径上，是这道题从不可行到可行的转折点。

面试视角：先说清楚题目其实是三个条件的合取以及为什么「路径有限」等价于「无环」，再给出三色 DFS，并主动解释为什么不需要「已确认不安全」这第四种状态；如果面试官追问非递归写法，可以补充用拓扑排序反向推导，或者用显式栈模拟递归以规避一万层的栈深风险。

易错点总结

只用一个布尔 visited 判环：n = 3、edges = [[0,1],[0,2],[1,2]]、source = 0、destination = 2 中节点 2 被两条不同路径先后访问，第二次会被误判成环，返回 false，正确答案是 true。

染灰的时机放在遍历后继之后：n = 2、edges = [[0,1],[1,0]]、source = 0、destination = 1 时递归回到节点 0 看到的状态仍是 0，环检测失效，程序无限递归直到栈溢出。

忘记「出度为 0 必须是终点」这一条，直接对空邻接表返回 true：n = 2、edges = [[0,1]]、source = 0、destination = 0 会误判为 true，实际上从 0 出发会停在 1，而 1 不是终点，答案是 false。

没有检查终点是否有出边：n = 2、edges = [[0,1],[1,0]]、source = 0、destination = 1 中终点 1 还能走回 0，本解法靠环检测顺带否定了它；但如果有人为了「优化」而在递归入口加上 if (node == dest) return true，这个用例就会错误返回 true。

把后继循环写成「有一个后继安全就返回 true」：n = 3、edges = [[0,1],[0,2],[1,2]]、source = 0、destination = 1 会因为第一个后继 1 合法就返回 true，忽略了走向 2 的那条坏路径，正确答案是 false。

在返回 false 前把状态复位成 0 却仍复用黑色缓存：n = 4、edges = [[0,1],[1,2],[2,1],[0,3]] 这类图会让同一段子图被反复展开，虽然结果仍对，但复杂度退化到指数级。

递归结束后把状态统一置回 0（标准回溯写法）：n 较大且分支密集时，例如一条链上挂满交叉边，记忆化完全失效，测试用例直接超时。

Java 里建图时忘了先为 n 个节点补齐空列表：n = 3、edges = [[0,1]] 时 graph.get(2) 会抛出下标越界，因为列表里只塞进了不足 n 个元素。

直接把 edges 当无向图双向建边：n = 2、edges = [[0,1]]、source = 0、destination = 1 会凭空造出 1 到 0 的反向边，形成环并返回 false。

忽略递归深度上限：节点数一万且图退化成一条链时，edges = [[0,1],[1,2],...,[9998,9999]] 会压出一万层栈帧，Java 默认栈大小下有溢出风险，面试中应主动提出可改用显式栈。

相似题目

题目	难度	考察点
133. 克隆图	中等	同为图遍历，但用哈希表记录映射以避免重复建点
207. 课程表	中等	只判有向图是否有环，可用入度队列做拓扑排序
210. 课程表 II	中等	在判环基础上还要输出一个合法拓扑序
323. 无向图中连通分量的数目	中等	无向图连通性统计，并查集比深搜更直接
329. 矩阵中的最长递增路径	困难	同样把结论记忆化在节点上，但求的是最长长度而非布尔判定
332. 重新安排行程	困难	要求真正输出一条经过所有边的路径，考察欧拉路径的后序构造
684. 冗余连接	中等	找出使无向图成环的那条边，靠并查集在加边时检测
785. 判断二分图	中等	遍历时给节点染两色，冲突即失败，标记的语义换成了分组
797. 所有可能的路径	中等	真的要枚举并返回全部路径，因图无环所以回溯可行
841. 钥匙和房间	中等	判断可达集合能否覆盖全部节点，不涉及环与终止性
1462. 课程表 IV	中等	需要回答任意两点间的可达性查询，靠传递闭包或按拓扑序合并集合