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

Categories:

题目描述
思路分析
1. 解法一：DFS + 访问状态（推荐）
相似题目

题目描述

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

思路分析

解法一：DFS + 访问状态（推荐）

核心思路：

构建邻接表并进行 DFS。

对每个节点记录状态：0 未访问，1 正在访问，2 已确认安全。

若遇到非终点的出度为 0 节点，或检测到环，则返回 false。

复杂度分析：

时间复杂度：O(n+m)，其中 n 为节点数，m 为边数。

空间复杂度：O(n+m)，用于图存储与递归栈。

import java.util.ArrayList;
import java.util.List;

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[] 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 {
	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)
}

相似题目

题目	难度	考察点
1059. 从起点到终点的所有路径	中等	DFS、状态标记
797. 所有可能的路径	中等	DFS
207. 课程表	中等	拓扑排序、DFS
210. 课程表 II	中等	拓扑排序
785. 判断二分图	中等	DFS/BFS

本文作者: HGNULB

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