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

2022-03-30 HGNULB 约 6 分钟

文章信息 8 个分类 2 个标签

分类

LeetCode CodeTop 中等未解决会员题 2-5 字节美团

题目描述

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

题意分析

判断从 source 出发的所有走法是否都能在有限步后停在 destination。找到一条到达目标的路径还不够：只要能走到其他无出边节点，或能进入一个环一直绕下去，就应返回 false。只需检查起点可达的部分。

解法：显式栈 + 三状态 DFS

核心思路

[!blue]

从一个节点出发的所有路径都符合要求，称这个节点安全。无出边节点只有在它就是 destination 时才安全；有出边节点则必须让每个后继都安全。这个依赖关系适合用 DFS，先验证后继，再确认当前节点。

state 分为三种：0 表示还未访问，1 表示正在当前 DFS 路径上，2 表示全部后继已验证、节点安全。沿边再次遇到状态 1 的节点，就能从当前路径回到祖先，形成可反复走的环；遇到状态 2 则只是重复到达已经验证的后缀，可以直接复用结论。

用显式栈模拟递归，每个栈帧保存当前节点和下一条待检查出边的下标。一次只沿一条边深入，进入孩子之前先推进父帧的下标，孩子处理完后就能接着检查下一条边。全部出边通过后才将节点标为 2 并出栈，所以栈中的状态 1 节点始终构成一条祖先路径，而不会混入尚未访问的兄弟节点。

任意失败分支都立即返回 false。若起点最终安全，说明可达部分没有环，而且所有路径的终止点都是目标；有限图中没有环就不可能无限行走，因此所有路径都会在目标结束。

解题步骤

建立有向邻接表，将 source 标为 1，以待检查出边下标 0 入栈。

查看栈顶：若当前节点无出边且不是目标，立即返回 false。

若当前帧已检查完全部出边，将节点标为 2 并出栈。

否则取下一条边，并推进帧内下标。后继为状态 1 时返回 false，为状态 2 时跳过，为状态 0 时标为 1 并入栈。

栈全部清空说明起点已通过验证，返回 true。

代码实现

class Solution {
    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[] edge : edges) {
            graph.get(edge[0]).add(edge[1]);
        }

        int[] state = new int[n];
        Deque<int[]> stack = new ArrayDeque<>();

        // 一表示当前栈上的活动路径，二表示全部后继已证实安全。
        state[source] = 1;
        stack.push(new int[] {
            source,
            0
        });

        while (!stack.isEmpty()) {
            int[] frame = stack.peek();
            int node = frame[0];

            if (graph.get(node).isEmpty() && node != destination) {
                return false;
            }

            if (frame[1] == graph.get(node).size()) {
                // 所有出边检查完成后才标安全，不能提前标记兄弟节点。
                state[node] = 2;
                stack.pop();
                continue;
            }

            // 先记录下一次要检查的出边，再沿当前边深入。
            int next = graph.get(node).get(frame[1]++);

            // 边回到活动路径形成环，即使另有目标出口也失败。
            if (state[next] == 1) {
                return false;
            }

            // 安全后缀直接复用，不再展开。
            if (state[next] == 2) {
                continue;
            }

            state[next] = 1;
            stack.push(new int[] {
                next,
                0
            });
        }

        return true;
    }
}

func leadsToDestination(n int, edges [][]int, source int, destination int) bool {
    graph := make([][]int, n)
    for _, edge := range edges {
        graph[edge[0]] = append(graph[edge[0]], edge[1])
    }

    type frame struct {
        node int
        next int
    }
    state := make([]int, n)
    // 一表示当前栈上的活动路径，二表示全部后继已证实安全。
    state[source] = 1
    stack := []frame{
        {source, 0},
    }
    for len(stack) > 0 {
        top := len(stack) - 1
        node := stack[top].node
        if len(graph[node]) == 0 && node != destination {
            return false
        }
        if stack[top].next == len(graph[node]) {
            // 所有出边检查完成后才标安全，不能提前标记兄弟节点。
            state[node] = 2
            stack = stack[:top]
            continue
        }

        next := graph[node][stack[top].next]
        // 先记录下一次要检查的出边，再沿当前边深入。
        stack[top].next++
        // 边回到活动路径形成环，即使另有目标出口也失败。
        if state[next] == 1 {
            return false
        }
        // 安全后缀直接复用，不再展开。
        if state[next] == 2 {
            continue
        }
        state[next] = 1
        stack = append(stack, frame{next, 0})
    }
    return true
}

复杂度分析

时间复杂度：$O(n+E)$，其中 n 为节点数、E 为边数；建图后，每个可达节点最多展开一次，每条出边最多检查一次。

空间复杂度：$O(n+E)$，邻接表、状态与遍历栈。

关键点总结

[!green]

正在访问只指当前栈上的路径，尚未进入的兄弟节点不能提前标成活动状态。

所有后继都要安全，找到一条到达目标的路还不够。

可达环即使另有出口到目标，也能选择一直绕环，因此仍不合格。

易错点总结

[!yellow]

把全部后继一次性标成正在访问，会把兄弟之间的合法连接误判成环。

后继尚未全部验证就标安全，会放过包含坏路径的节点。

到达目标就无条件成功，会漏掉目标仍能继续离开的情况。

起点没有出边时，只有 source == destination 才成功；不可达的环或错误终止点不影响答案。

相似题目

题目	难度	关联与区别
802. 找到最终的安全状态	中等	两题都要求所有路径最终终止，本题还要求所有终止点都是指定destination。
207. 课程表	中等	同样需要识别环，本题只关心起点可达部分并同时排除错误终止点。

转载与许可

作者 HGNULB

链接 https://hgnulb.github.io/blog/2022/11960605

许可本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！