[Swift-2019力扣杯春季初赛]4.从始点到终点的所有路径

OStack程序员社区-中国程序员成长平台 › 门户 › 编程› 移动开发›Swift 教程

原作者: [db:作者] 来自: [db:来源] 收藏邀请

★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
➤微信公众号：山青咏芝（shanqingyongzhi）
➤博客园地址：山青咏芝（https://www.cnblogs.com/strengthen/）
➤GitHub地址：https://github.com/strengthen/LeetCode
➤原文地址：
➤如果链接不是山青咏芝的博客园地址，则可能是爬取作者的文章。
➤原文已修改更新！强烈建议点击原文地址阅读！支持作者！支持原创！
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★

热烈欢迎，请直接点击！！！

进入博主App Store主页，下载使用各个作品！！！

注：博主将坚持每月上线一个新app！！！

给定有向图的边 edges，以及该图的始点 source 和目标终点 destination，确定从始点 source 出发的所有路径是否最终结束于目标终点 destination，即：

从始点 source 到目标终点 destination 存在至少一条路径
如果存在从始点 source 到没有出边的节点的路径，则该节点就是路径终点。
从始点source到目标终点 destination 可能路径数是有限数字

当从始点 source 出发的所有路径都可以到达目标终点 destination 时返回 true，否则返回 false。

示例 1：

输入：n = 3, edges = [[0,1],[0,2]], source = 0, destination = 2
输出：false
说明：节点 1 和节点 2 都可以到达，但也会卡在那里。

示例 2：

输入：n = 4, edges = [[0,1],[0,3],[1,2],[2,1]], source = 0, destination = 3
输出：false
说明：有两种可能：在节点 3 处结束，或是在节点 1 和节点 2 之间无限循环。

示例 3：

输入：n = 4, edges = [[0,1],[0,2],[1,3],[2,3]], source = 0, destination = 3
输出：true

示例 4：

输入：n = 3, edges = [[0,1],[1,1],[1,2]], source = 0, destination = 2
输出：false
说明：从始点出发的所有路径都在目标终点结束，但存在无限多的路径，如 0-1-2，0-1-1-2，0-1-1-1-2，0-1-1-1-1-2 等。

示例 5：

输入：n = 2, edges = [[0,1],[1,1]], source = 0, destination = 1
输出：false
说明：在目标节点上存在无限的自环。

提示：

给定的图中可能带有自环和平行边。
图中的节点数 n 介于 1 和 10000 之间。
图中的边数在 0 到 10000 之间。
0 <= edges.length <= 10000
edges[i].length == 2
0 <= source <= n - 1
0 <= destination <= n - 1

764ms

 1 class Solution {
 2     func leadsToDestination(_ n: Int, _ edges: [[Int]], _ source: Int, _ destination: Int) -> Bool {
 3         var graph:[Int:[Int]] = [Int:[Int]]()
 4         var path:Set<Int> = Set<Int>()
 5         var qu:[Int] = [Int]()
 6         for e in edges
 7         {
 8             graph[e[0],default:[Int]()].append(e[1])
 9         }
10         if graph[destination] != nil
11         {
12             return false
13         }
14         if n == 1
15         {
16             return true
17         }
18         path.insert(source)
19         if !dfs(&graph,&path,source,destination)
20         {
21             return false
22         }
23         return true 
24     }
25     
26     func dfs(_ graph:inout [Int:[Int]],_ path:inout Set<Int>,_ last:Int,_ destination:Int) -> Bool
27     {
28         if graph[last] == nil
29         {
30             return false
31         }
32         for e in graph[last,default:[Int]()]
33         {
34             if path.contains(e)
35             {
36                 return false
37             }
38             else
39             {
40                 if e == destination
41                 {
42                     continue
43                 }
44                 path.insert(e)
45                 if !dfs(&graph,&path,e,destination)
46                 {
47                     return false
48                 }
49                 path.remove(e)
50             }
51         }
52         return true        
53     }
54 }