[Swift]LeetCode685.冗余连接II|RedundantConnectionII

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

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

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

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

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

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

In this problem, a rooted tree is a directed graph such that, there is exactly one node (the root) for which all other nodes are descendants of this node, plus every node has exactly one parent, except for the root node which has no parents.

The given input is a directed graph that started as a rooted tree with N nodes (with distinct values 1, 2, ..., N), with one additional directed edge added. The added edge has two different vertices chosen from 1 to N, and was not an edge that already existed.

The resulting graph is given as a 2D-array of edges. Each element of edges is a pair [u, v] that represents a directed edge connecting nodes u and v, where u is a parent of child v.

Return an edge that can be removed so that the resulting graph is a rooted tree of N nodes. If there are multiple answers, return the answer that occurs last in the given 2D-array.

Example 1:

Input: [[1,2], [1,3], [2,3]]
Output: [2,3]
Explanation: The given directed graph will be like this:
  1
 / \
v   v
2-->3

Example 2:

Input: [[1,2], [2,3], [3,4], [4,1], [1,5]]
Output: [4,1]
Explanation: The given directed graph will be like this:
5 <- 1 -> 2
     ^    |
     |    v
     4 <- 3

Note:

The size of the input 2D-array will be between 3 and 1000.
Every integer represented in the 2D-array will be between 1 and N, where N is the size of the input array.

在本问题中，有根树指满足以下条件的有向图。该树只有一个根节点，所有其他节点都是该根节点的后继。每一个节点只有一个父节点，除了根节点没有父节点。

输入一个有向图，该图由一个有着N个节点 (节点值不重复1, 2, ..., N) 的树及一条附加的边构成。附加的边的两个顶点包含在1到N中间，这条附加的边不属于树中已存在的边。

结果图是一个以边组成的二维数组。每一个边 的元素是一对 [u, v]，用以表示有向图中连接顶点 u and v和顶点的边，其中父节点u是子节点v的一个父节点。

返回一条能删除的边，使得剩下的图是有N个节点的有根树。若有多个答案，返回最后出现在给定二维数组的答案。

示例 1:

输入: [[1,2], [1,3], [2,3]]
输出: [2,3]
解释: 给定的有向图如下:
  1
 / \
v   v
2-->3

示例 2:

输入: [[1,2], [2,3], [3,4], [4,1], [1,5]]
输出: [4,1]
解释: 给定的有向图如下:
5 <- 1 -> 2
     ^    |
     |    v
     4 <- 3

注意:

二维数组大小的在3到1000范围内。
二维数组中的每个整数在1到N之间，其中 N 是二维数组的大小。

36ms

 1 class Solution {
 2     func findRedundantDirectedConnection(_ edges: [[Int]]) -> [Int] {
 3         guard edges.isEmpty == false else {
 4             return []
 5         }
 6         var parents: [Int] = []
 7         
 8         var res1: [Int] = []
 9         var res2: [Int] = []
10         
11         for i in 0...edges.count {
12             parents.append(i)
13         }
14         for edge in edges {
15             let x = edge[0]
16             let y = edge[1]
17             let rootX = find(&parents, x)
18             let rootY = find(&parents, y)
19             if rootX != rootY {
20                 if rootY != y {
21                     res1 = edge
22                 } else {
23                     parents[y] = x
24                 }
25             } else {
26                 res2 = edge
27             }
28         }
29         if res1.isEmpty == true {
30             return res2
31         }
32         if res2.isEmpty == true {
33             return res1
34         }
35         
36         for edge in edges {
37             if edge[1] == res1[1] {
38                 return edge
39             }
40         }
41         return []
42     }
43     
44     private func find(_ parents: inout [Int], _ val: Int) -> Int {
45         if parents[val] != val {
46             parents[val] = find(&parents, parents[val])
47         }
48         return parents[val]
49     }
50 }

40ms

 1 class Solution {
 2     func findRedundantDirectedConnection(_ edges: [[Int]]) -> [Int] {
 3         guard edges.isEmpty == false else {
 4             return []
 5         }
 6         var parents: [Int] = []
 7         
 8         var res1: [Int] = []
 9         var res2: [Int] = []
10         
11         for i in 0...edges.count {
12             parents.append(i)
13         }
14         for edge in edges {
15             let x = edge[0]
16             let y = edge[1]
17             let rootX = find(parents, x)
18             let rootY = find(parents, y)
19             if rootX != rootY {
20                 if rootY != y {
21                     res1 = edge
22                 } else {
23                     parents[y] = x
24                 }
25             } else {
26                 res2 = edge
27             }
28         }
29         if res1.isEmpty == true {
30             return res2
31         }
32         if res2.isEmpty == true {
33             return res1
34         }
35         
36         for edge in edges {
37             if edge[1] == res1[1] {
38                 return edge
39             }
40         }
41         return []
42     }
43     
44     private func find(_ parents: [Int], _ val: Int) -> Int {
45         if val == parents[val] {
46             return val
47         }
48         return find(parents, parents[val])
49     }
50 }

Runtime: 44 ms

Memory Usage: 19.1 MB

 1 class Solution {
 2     func findRedundantDirectedConnection(_ edges: [[Int]]) -> [Int] {
 3         var edges = edges
 4         var n:Int = edges.count
 5         var root:[Int] = [Int](repeating:0,count:n + 1)
 6         var first:[Int] = [Int]()
 7         var second:[Int] = [Int]()
 8         for i in 0..<edges.count
 9         {
10             if root[edges[i][1]] == 0
11             {
12                 root[edges[i][1]] = edges[i][0]
13             }
14             else
15             {
16                 first = [root[edges[i][1]], edges[i][1]]
17                 second = edges[i]
18                 edges[i][1] = 0
19             }
20         }
21         for i in 0...n
22         {
23             root[i] = i
24         }
25         for edge in edges
26         {
27             if edge[1] == 0 {continue}
28             var x:Int = getRoot(&root, edge[0])
29             var y:Int = getRoot(&root, edge[1])
30             if x == y
31             {
32                 return first.isEmpty ? edge : first
33             }
34             root[x] = y            
35         }
36         return second
37     }
38     
39     func getRoot(_ root:inout [Int],_ i:Int) -> Int
40     {
41         return i == root[i] ? i : getRoot(&root, root[i])
42     }
43 }

52ms

 1 class Solution {
 2     var parents = [Int: Int]()
 3     var candidate1 = [-1, -1]
 4     var candidate2 = [-1, -1]
 5     
 6     func findRedundantDirectedConnection(_ edges: [[Int]]) -> [Int] {
 7         var edges = edges
 8         // ****** Step 1: Check if there is a 2-parent situation. ******
 9         for i in 0..<edges.count {
10             let parent = edges[i][0]
11             let child = edges[i][1]
12             if let existedParent = parents[child] {
13                   // If there is already an existed parent for the current child, this means we have found a 2-parent situation.
14                 // Set candidate1 to the previously-found edge.
15                 candidate1 = [existedParent, child]
16                 // Set candidate2 to the current edge.
17                 candidate2 = edges[i]
18                 // Invalidate the curent edge.
19                 edges[i][1] = -1
20             } else {
21                 // If there is no 2-parent situation, we record the parent for each child.
22                 parents[child] = parent
23             }
24         }
25         
26         // ****** Step2: Perform union-find to find if there is any cycles. ******
27         // Reset parent dictionary.
28         parents = [Int: Int]()
29         // Perform union-find.
30         var foundEdge: [Int]?
31         for edge in edges {
32             guard edge[1] != -1 else {
33                 continue
34             }
35             if let foundEdge = union(edge[0], edge[1]) {
36                 return foundEdge
37             }
38         }
39         // If we reach this point, that means we previously invalidated the corrent "wrong" edge and there is no cycle,
40         // which is situation #1, just return candidate2.
41         return candidate2
42     }
43     
44     private func union(_ x: Int, _ y: Int) -> [Int]? {
45         let xParnet = find(x)
46         let yParent = find(y)
47         guard xParnet != yParent else {
48             // If we have found a cycle...
49             if candidate1[0] == -1 {
50                 // If there is no 2-parent situation at all, which is situation #2, return the current edge.
51                 return [x, y]
52             } else {
53                  // If there is a 2-parent situation, which is situation #3, return candidate 1.
54                 return candidate1
55             }
56         }
57         // If no cycle is found, we are good and return nothing.
58         parents[yParent] = xParnet
59         return nil
60     }
61     
62     private func find(_ x: Int) -> Int {
63         // Recursively find the parent or return the node itself if this node has no parent.
64         if parents[x] == nil {
65             return x
66         }
67         return find(parents[x]!)
68     }
69 }

56ms

 1 class Solution {
 2     func findRedundantDirectedConnection(_ edges: [[Int]]) -> [Int] {
 3       var adjacentInfo: [Int: Set<Int>] = [:]
 4       var parentInfo: [Int: [Int]] = [:]
 5       var target: Int = -1
 6       for edge in edges {
 7         var adjacentSet: Set<Int>
 8         if let adjSet = adjacentInfo[edge[0]] {
 9           adjacentSet = adjSet
10         } else {
11           adjacentSet = Set()
12         }
13         adjacentSet.insert(edge[1])
14         adjacentInfo[edge[0]] = adjacentSet
15         
16         if var parents = parentInfo[edge[1]] {
17           target = edge[1]
18           parents.append(edge[0])
19           parentInfo[edge[1]] = parents
20         } else{
21           parentInfo[edge[1]] = [edge[0]]
22         }
23       }
24       
25       if target != -1, let parents = parentInfo[target] {
26         var root: Int = parents.first!
27         for key in adjacentInfo.keys {
28           if parentInfo[key] == nil {
29             root = key
30             break
31           }
32         }
33         
34         let candidate = parents.last!
35         
36         var removed = adjacentInfo[candidate]
37         removed?.remove(target)
38         adjacentInfo[candidate] = removed ?? []
39         if hasPath(from: root, to: target, info: adjacentInfo) {
40           return [candidate, target]
41         } else {
42           return [parents.first!, target]
43         }
44       }
45       
46       for edge in edges.reversed() {
47         if hasPath(from: edge[1], to: edge[0], info: adjacentInfo) {
48           return edge
49         }
50       }
51       return []
52     }
53     func hasPath(from: Int, to: Int, info: [Int: Set<Int>]) -> Bool {
54       var visited: Set<Int> = Set()
55       var queue: [Int] = [from]
56       while queue.count > 0 {
57         let current = queue.first!
58         queue.remove(at: 0)
59         visited.insert(current)
60         
61         if current == to {
62           return true
63         }
64         guard let adjs = info[current] else { continue }
65         for neighbor in adjs {
66           if visited.contains(neighbor) == false {
67             queue.append(neighbor)
68           }
69         }
70       }
71       return false
72     }
73 }