• 设为首页
  • 点击收藏
  • 手机版
    手机扫一扫访问
    迪恩网络手机版
  • 关注官方公众号
    微信扫一扫关注
    公众号

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

原作者: [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
说明:在目标节点上存在无限的自环。

提示:

  1. 给定的图中可能带有自环和平行边。
  2. 图中的节点数 n 介于 1 和 10000 之间。
  3. 图中的边数在 0 到 10000 之间。
  4. 0 <= edges.length <= 10000
  5. edges[i].length == 2
  6. 0 <= source <= n - 1
  7. 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 }

 


鲜花

握手

雷人

路过

鸡蛋
该文章已有0人参与评论

请发表评论

全部评论

专题导读
上一篇:
swift-WKWebView发布时间:2022-07-13
下一篇:
swift版的GCD封装发布时间:2022-07-13
热门推荐
热门话题
阅读排行榜

扫描微信二维码

查看手机版网站

随时了解更新最新资讯

139-2527-9053

在线客服(服务时间 9:00~18:00)

在线QQ客服
地址:深圳市南山区西丽大学城创智工业园
电邮:jeky_zhao#qq.com
移动电话:139-2527-9053

Powered by 互联科技 X3.4© 2001-2213 极客世界.|Sitemap