LeetCode-python 面试题04.01. 节点间通路

题目链接
难度：中等       类型： DFS

节点间通路。给定有向图，设计一个算法，找出两个节点之间是否存在一条路径。

示例：

输入：n = 3, graph = [[0, 1], [0, 2], [1, 2], [1, 2]], start = 0, target = 2
输出：true

解题思路

从起始点开始，一步一步走就好了

代码实现

基本的dfs解法

class Solution:
    def findWhetherExistsPath(self, n: int, graph: List[List[int]], start: int, target: int) -> bool:
        visited = set()
        path = collections.defaultdict(set)
        for x, y in graph:
            path[x].add(y)

        def dfs(cur_start):
            if cur_start in visited:
                return False
            if target in path[cur_start]:
                return True
            visited.add(cur_start)

            for new_start in path[cur_start]:
                if dfs(new_start):
                    return True
            return False

        return dfs(start)