[Swift]LeetCode802.找到最终的安全状态|FindEventualSafeStates

OGeek|极客世界-中国程序员成长平台 › 门户 › 编程› 移动开发›Swift 教程

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

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

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

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

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

In a directed graph, we start at some node and every turn, walk along a directed edge of the graph. If we reach a node that is terminal (that is, it has no outgoing directed edges), we stop.

Now, say our starting node is eventually safe if and only if we must eventually walk to a terminal node. More specifically, there exists a natural number K so that for any choice of where to walk, we must have stopped at a terminal node in less than K steps.

Which nodes are eventually safe? Return them as an array in sorted order.

The directed graph has N nodes with labels 0, 1, ..., N-1, where N is the length of graph. The graph is given in the following form: graph[i] is a list of labels j such that (i, j) is a directed edge of the graph.

Example:
Input: graph = [[1,2],[2,3],[5],[0],[5],[],[]]
Output: [2,4,5,6]
Here is a diagram of the above graph.

Note:

graph will have length at most 10000.
The number of edges in the graph will not exceed 32000.
Each graph[i] will be a sorted list of different integers, chosen within the range [0, graph.length - 1].

在有向图中, 我们从某个节点和每个转向处开始, 沿着图的有向边走。如果我们到达的节点是终点 (即它没有连出的有向边), 我们停止。

现在, 如果我们最后能走到终点，那么我们的起始节点是最终安全的。更具体地说, 存在一个自然数 K, 无论选择从哪里开始行走, 我们走了不到 K 步后必能停止在一个终点。

哪些节点最终是安全的？结果返回一个有序的数组。

该有向图有 N 个节点，标签为 0, 1, ..., N-1, 其中 N是 graph 的节点数. 图以以下的形式给出: graph[i] 是节点 j 的一个列表，满足 (i, j) 是图的一条有向边。

示例：
输入：graph = [[1,2],[2,3],[5],[0],[5],[],[]]
输出：[2,4,5,6]
这里是上图的示意图。

提示：

graph 节点数不超过 10000.
图的边数不会超过 32000.
每个 graph[i] 被排序为不同的整数列表，在区间 [0, graph.length - 1] 中选取。

Runtime: 796 ms

Memory Usage: 19.7 MB

 1 class Solution {
 2     func eventualSafeNodes(_ graph: [[Int]]) -> [Int] {
 3         var graph = graph
 4         var n:Int = graph.count
 5         // 0 white, 1 gray, 2 black
 6         var res:[Int] = [Int]()
 7         var color:[Int] = [Int](repeating:0,count:n)
 8         for i in 0..<n
 9         {
10             if helper(&graph, i, &color)
11             {
12                 res.append(i)
13             }
14         }
15         return res
16     }
17     
18     func helper(_ graph:inout [[Int]],_ cur:Int,_ color:inout [Int]) -> Bool
19     {
20         if color[cur] > 0
21         {
22             return color[cur] == 2
23         }
24         color[cur] = 1
25         for i in graph[cur]
26         {
27             if color[i] == 2 {continue}
28             if color[i] == 1 || !helper(&graph, i, &color)
29             {
30                 return false
31             }
32         }
33         color[cur] = 2
34         return true
35     }
36 }

1116ms

 1 class Solution {
 2     func eventualSafeNodes(_ graph: [[Int]]) -> [Int] {
 3         var values: [Int?] = Array(repeatElement(nil, count: graph.count))
 4         for nodes in graph.enumerated() {
 5             dfs(graph, nodes.offset, &values)
 6         }
 7         return values.enumerated().filter{$0.element == 1}.map{$0.offset}
 8     }
 9     
10     // nil = not visited
11     // 1 = safe
12     // 2 = cycle/visited
13     func dfs(_ graph: [[Int]], _ node: Int, _ values : inout [Int?]) -> Bool {
14         if values[node] == 2 {return false}
15         if values[node] == 1 {return true}
16         values[node] = 2
17         for neighbor in graph[node] {
18             if !dfs(graph, neighbor, &values) {
19                 values[node] = 2
20                 return false
21             }
22         }
23         values[node] = 1
24         return true
25     }
26 }

1156ms

 1 class Solution {
 2     func eventualSafeNodes(_ graph: [[Int]]) -> [Int] {
 3         var outDegree = graph.map { $0.count }
 4         var safeVertices = outDegree.enumerated().compactMap { $0.1 == 0 ? $0.0 : nil }
 5         var adj = [Int: [Int]]()
 6         for (u, edges) in graph.enumerated() {
 7             for v in edges {
 8                 adj[v, default: []].append(u)
 9             }
10         }
11 
12         var result = [Int]()
13         var i = 0
14         while i < safeVertices.count {
15             result.append(safeVertices[i])
16             for v in adj[safeVertices[i], default: []] {
17                 outDegree[v] -= 1
18                 if outDegree[v] == 0 {
19                     safeVertices.append(v)
20                 }
21             }
22             i += 1
23         }
24         return result.sorted(by: <)
25     }
26 }