[Swift]LeetCode684. 冗余连接 | Redundant Connection
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
➤微信公众号:山青咏芝(shanqingyongzhi)
➤博客园地址:山青咏芝(https://www.cnblogs.com/strengthen/)
➤GitHub地址:https://github.com/strengthen/LeetCode
➤原文地址: https://www.cnblogs.com/strengthen/p/10500242.html
➤如果链接不是山青咏芝的博客园地址,则可能是爬取作者的文章。
➤原文已修改更新!强烈建议点击原文地址阅读!支持作者!支持原创!
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
In this problem, a tree is an undirected graph that is connected and has no cycles.
The given input is a graph that started as a tree with N nodes (with distinct values 1, 2, ..., N), with one additional 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]
with u < v
, that represents an undirected edge connecting nodes u
and v
.
Return an edge that can be removed so that the resulting graph is a tree of N nodes. If there are multiple answers, return the answer that occurs last in the given 2D-array. The answer edge [u, v]
should be in the same format, with u < v
.
Example 1:
Input: [[1,2], [1,3], [2,3]] Output: [2,3] Explanation: The given undirected graph will be like this: 1 / \ 2 - 3
Example 2:
Input: [[1,2], [2,3], [3,4], [1,4], [1,5]] Output: [1,4] Explanation: The given undirected graph will be like this: 5 - 1 - 2 | | 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.
Update (2017-09-26):
We have overhauled the problem description + test cases and specified clearly the graph is an undirectedgraph. For the directed graph follow up please see Redundant Connection II). We apologize for any inconvenience caused.
在本问题中, 树指的是一个连通且无环的无向图。
输入一个图,该图由一个有着N个节点 (节点值不重复1, 2, ..., N) 的树及一条附加的边构成。附加的边的两个顶点包含在1到N中间,这条附加的边不属于树中已存在的边。
结果图是一个以边
组成的二维数组。每一个边
的元素是一对[u, v]
,满足 u < v
,表示连接顶点u
和v
的无向图的边。
返回一条可以删去的边,使得结果图是一个有着N个节点的树。如果有多个答案,则返回二维数组中最后出现的边。答案边 [u, v]
应满足相同的格式 u < v
。
示例 1:
输入: [[1,2], [1,3], [2,3]] 输出: [2,3] 解释: 给定的无向图为: 1 / \ 2 - 3
示例 2:
输入: [[1,2], [2,3], [3,4], [1,4], [1,5]] 输出: [1,4] 解释: 给定的无向图为: 5 - 1 - 2 | | 4 - 3
注意:
- 输入的二维数组大小在 3 到 1000。
- 二维数组中的整数在1到N之间,其中N是输入数组的大小。
更新(2017-09-26):
我们已经重新检查了问题描述及测试用例,明确图是无向 图。对于有向图详见冗余连接II。对于造成任何不便,我们深感歉意。
Runtime: 28 ms
Memory Usage: 18.9 MB
1 class Solution { 2 func findRedundantConnection(_ edges: [[Int]]) -> [Int] { 3 var root:[Int] = [Int](repeating:-1,count:2001) 4 for edge in edges 5 { 6 var x:Int = find(&root, edge[0]) 7 var y:Int = find(&root, edge[1]) 8 if x == y {return edge} 9 root[x] = y 10 } 11 return [Int]() 12 } 13 14 func find (_ root:inout [Int],_ i:Int) -> Int 15 { 16 var i = i 17 while (root[i] != -1) 18 { 19 i = root[i] 20 } 21 return i 22 } 23 }
32ms
1 class Solution { 2 func findRedundantConnection(_ edges: [[Int]]) -> [Int] { 3 guard edges.isEmpty == false else { 4 return [] 5 } 6 let n = edges.count 7 var parents: [Int] = [] 8 for i in 0...n { 9 parents.append(i) 10 } 11 for edge in edges { 12 let first = edge[0] 13 let second = edge[1] 14 let p1 = find(parents, first) 15 let p2 = find(parents, second) 16 if p1 == p2 { 17 return edge 18 } 19 parents[p2] = p1 20 } 21 return [] 22 } 23 24 private func find(_ parents: [Int], _ val: Int) -> Int { 25 if parents[val] == val { 26 return val 27 } 28 return find(parents, parents[val]) 29 } 30 }
48ms
1 class Solution { 2 // s1: union find 3 func findRedundantConnection(_ edges: [[Int]]) -> [Int] { 4 var uf = UnionFind(n: edges.count+1) 5 for con in edges { 6 let s = con[0] 7 let e = con[1] 8 if uf.union(s, e) == false { 9 return con 10 } 11 } 12 return [] 13 } 14 } 15 16 class UnionFind { 17 public var parents = [Int]() 18 private var ranks = [Int]() 19 public var count: Int = 0 20 init(n: Int) { 21 for i in 0..<n { 22 parents.append(i) 23 ranks.append(1) 24 } 25 } 26 27 func find(_ x: Int) -> Int { 28 var x = x 29 if parents[x] != x { 30 parents[x] = find(parents[x]) 31 } 32 return parents[x] 33 } 34 /* 35 1 2 3 36 5 6 37 */ 38 func union(_ x: Int, _ y: Int) -> Bool { 39 let px = find(x) 40 let py = find(y) 41 if px == py { 42 return false 43 } 44 count -= 1 45 if ranks[x] > ranks[y] { 46 parents[py] = px 47 } else if ranks[x] < ranks[y] { 48 parents[px] = py 49 } else { 50 parents[py] = px 51 ranks[px] += 1 52 } 53 return true 54 } 55 }
52ms
1 class Solution { 2 func findRedundantConnection(_ edges: [[Int]]) -> [Int] { 3 guard edges.count > 0 else { return [0,0] } 4 5 var totalNode = edges.count + 1 6 7 var group: [Int] = [] 8 var groupLevel: [Int] = [] 9 10 for i in 0..<totalNode { 11 group.append(i) 12 groupLevel.append(0) 13 } 14 15 var extraEdge:[Int] = [] 16 17 for edge in edges { 18 var nodeX = edge[0] 19 var nodeY = edge[1] 20 21 var pNodeX = findParent(nodeX, &group) 22 var pNodeY = findParent(nodeY, &group) 23 if pNodeX != pNodeY { 24 if groupLevel[pNodeX] > groupLevel[pNodeY] { 25 group[pNodeY] = pNodeX 26 }else if groupLevel[pNodeX] < groupLevel[pNodeY] { 27 group[pNodeX] = pNodeY 28 }else { 29 group[pNodeY] = pNodeX 30 groupLevel[pNodeX] += 1 31 } 32 }else { 33 extraEdge = edge 34 } 35 } 36 return extraEdge 37 } 38 39 40 func findParent(_ node: Int, _ group: inout [Int]) -> Int { 41 var currentNode = node 42 while currentNode != group[currentNode] { 43 group[currentNode] = group[group[currentNode]] 44 currentNode = group[currentNode] 45 } 46 47 return currentNode 48 } 49 }
64ms
1 class Solution { 2 3 struct Edge { 4 var w: Int 5 var a: Int 6 var b: Int 7 } 8 9 func findRedundantConnection(_ _edges: [[Int]]) -> [Int] { 10 var wEdges = [Int: [(Int, Int)]]() 11 for (i, edge) in _edges.enumerated() { 12 wEdges[edge[0], default: []].append((edge[1], i)) 13 wEdges[edge[1], default: []].append((edge[0], i)) 14 } 15 var safe: Set<Int> = [] 16 var heap = Heap<((Int, Int), Int)>(sort: { 17 $0.1 < $1.1 18 }) 19 let source = _edges[0][0] 20 var edges = Set<[Int]>() 21 safe.insert(source) 22 for n in wEdges[source]! { 23 heap.insert( ((source, n.0), n.1) ) 24 } 25 while !heap.isEmpty { 26 let ((source, node), _) = heap.remove()! 27 safe.insert(node) 28 edges.insert([source, node]) 29 edges.insert([node, source]) 30 for n in wEdges[node]! { 31 if edges.contains( [n.0, node] ) { 32 33 } else if safe.contains(n.0) { 34 return [node, n.0].sorted() 35 } else { 36 heap.insert( ((node, n.0), n.1) ) 37 } 38 } 39 } 40 41 return _edges.last! 42 } 43 } 44 45 public struct Heap<T> { 46 47 /** The array that stores the heap's nodes. */ 48 var nodes = [T]() 49 50 /** 51 * Determines how to compare two nodes in the heap. 52 * Use '>' for a max-heap or '<' for a min-heap, 53 * or provide a comparing method if the heap is made 54 * of custom elements, for example tuples. 55 */ 56 private var orderCriteria: (T, T) -> Bool 57 58 /** 59 * Creates an empty heap. 60 * The sort function determines whether this is a min-heap or max-heap. 61 * For comparable data types, > makes a max-heap, < makes a min-heap. 62 */ 63 public init(sort: @escaping (T, T) -> Bool) { 64 self.orderCriteria = sort 65 } 66 67 /** 68 * Creates a heap from an array. The order of the array does not matter; 69 * the elements are inserted into the heap in the order determined by the 70 * sort function. For comparable data types, '>' makes a max-heap, 71 * '<' makes a min-heap. 72 */ 73 public init(array: [T], sort: @escaping (T, T) -> Bool) { 74 self.orderCriteria = sort 75 configureHeap(from: array) 76 } 77 78 /** 79 * Configures the max-heap or min-heap from an array, in a bottom-up manner. 80 * Performance: This runs pretty much in O(n). 81 */ 82 private mutating func configureHeap(from array: [T]) { 83 nodes = array 84 for i in stride(from: (nodes.count/2-1), through: 0, by: -1) { 85 shiftDown(i) 86 } 87 } 88 89 public var isEmpty: Bool { 90 return nodes.isEmpty 91 } 92 93 public var count: Int { 94 return nodes.count 95 } 96 97 /** 98 * Returns the index of the parent of the element at index i. 99 * The element at index 0 is the root of the tree and has no parent. 100 */ 101 @inline(__always) internal func parentIndex(ofIndex i: Int) -> Int { 102 return (i - 1) / 2 103 } 104 105 /** 106 * Returns the index of the left child of the element at index i. 107 * Note that this index can be greater than the heap size, in which case 108 * there is no left child. 109 */ 110 @inline(__always) internal func leftChildIndex(ofIndex i: Int) -> Int { 111 return 2*i + 1 112 } 113 114 /** 115 * Returns the index of the right child of the element at index i. 116 * Note that this index can be greater than the heap size, in which case 117 * there is no right child. 118 */ 119 @inline(__always) internal func rightChildIndex(ofIndex i: Int) -> Int { 120 return 2*i + 2 121 } 122 123 /** 124 * Returns the maximum value in the heap (for a max-heap) or the minimum 125 * value (for a min-heap). 126 */ 127 public func peek() -> T? { 128 return nodes.first 129 } 130 131 /** 132 * Adds a new value to the heap. This reorders the heap so that the max-heap 133 * or min-heap property still holds. Performance: O(log n). 134 */ 135 public mutating func insert(_ value: T) { 136 nodes.append(value) 137 shiftUp(nodes.count - 1) 138 } 139 140 /** 141 * Adds a sequence of values to the heap. This reorders the heap so that 142 * the max-heap or min-heap property still holds. Performance: O(log n). 143 */ 144 public mutating func insert<S: Sequence>(_ sequence: S) where S.Iterator.Element == T { 145 for value in sequence { 146 insert(value) 147 } 148 } 149 150 /** 151 * Allows you to change an element. This reorders the heap so that 152 * the max-heap or min-heap property still holds. 153 */ 154 public mutating func replace(index i: Int, value: T) { 155 guard i < nodes.count else { return } 156 157 remove(at: i) 158 insert(value) 159 } 160 161 /** 162 * Removes the root node from the heap. For a max-heap, this is the maximum 163 * value; for a min-heap it is the minimum value. Performance: O(log n). 164 */ 165 @discardableResult public mutating func remove() -> T? { 166 guard !nodes.isEmpty else { return nil } 167 168 if nodes.count == 1 { 169 return nodes.removeLast() 170 } else { 171 // Use the last node to replace the first one, then fix the heap by 172 // shifting this new first node into its proper position. 173 let value = nodes[0] 174 nodes[0] = nodes.removeLast() 175 shiftDown(0) 176 return value 177 } 178 } 179 180 /** 181 * Removes an arbitrary node from the heap. Performance: O(log n). 182 * Note that you need to know the node's index. 183 */ 184 @discardableResult public mutating func remove(at index: Int) -> T? { 185 guard index < nodes.count else { return nil } 186 187 let size = nodes.count - 1 188 if index != size { 189 nodes.swapAt(index, size) 190 shiftDown(from: index, until: size) 191 shiftUp(index) 192 } 193 return nodes.removeLast() 194 } 195 196 /** 197 * Takes a child node and looks at its parents; if a parent is not larger 198 * (max-heap) or not smaller (min-heap) than the child, we exchange them. 199 */ 200 internal mutating func shiftUp(_ index: Int) { 201 var childIndex = index 202 let child = nodes[childIndex] 203 var parentIndex = self.parentIndex(ofIndex: childIndex) 204 205 while childIndex > 0 && orderCriteria(child, nodes[parentIndex]) { 206 nodes[childIndex] = nodes[parentIndex] 207 childIndex = parentIndex 208 parentIndex = self.parentIndex(ofIndex: childIndex) 209 } 210 211 nodes[childIndex] = child 212 } 213 214 /** 215 * Looks at a parent node and makes sure it is still larger (max-heap) or 216 * smaller (min-heap) than its childeren. 217 */ 218 internal mutating func shiftDown(from index: Int, until endIndex: Int) { 219 let leftChildIndex = self.leftChildIndex(ofIndex: index) 220 let rightChildIndex = leftChildIndex + 1 221 222 // Figure out which comes first if we order them by the sort function: 223 // the parent, the left child, or the right child. If the parent comes 224 // first, we're done. If not, that element is out-of-place and we make 225 // it "float down" the tree until the heap property is restored. 226 var first = index 227 if leftChildIndex < endIndex && orderCriteria(nodes[leftChildIndex], nodes[first]) { 228 first = leftChildIndex 229 } 230 if rightChildIndex < endIndex && orderCriteria(nodes[rightChildIndex], nodes[first]) { 231 first = rightChildIndex 232 } 233 if first == index { return } 234 235 nodes.swapAt(index, first) 236 shiftDown(from: first, until: endIndex) 237 } 238 239 internal mutating func shiftDown(_ index: Int) { 240 shiftDown(from: index, until: nodes.count) 241 } 242 243 } 244 245 // MARK: - Searching 246 extension Heap where T: Equatable { 247 248 /** Get the index of a node in the heap. Performance: O(n). */ 249 public func index(of node: T) -> Int? { 250 return nodes.index(where: { $0 == node }) 251 } 252 253 /** Removes the first occurrence of a node from the heap. Performance: O(n log n). */ 254 @discardableResult public mutating func remove(node: T) -> T? { 255 if let index = index(of: node) { 256 return remove(at: index) 257 } 258 return nil 259 } 260 }
88ms
1 class Solution { 2 3 func findRedundantConnection(_ edges: [[Int]]) -> [Int] { 4 var N = 0 5 var graph = [Int: Set<Int>]() 6 for edge in edges { 7 graph[edge[0], default: []].insert(edge[1]) 8 graph[edge[1], default: []].insert(edge[0]) 9 N = max(N, edge[0], edge[1]) 10 } 11 let source = edges[0][0] 12 for edge in edges.reversed() { 13 if isConnected(graph, edge, source, N) { 14 return edge 15 } 16 } 17 return edges.last! 18 } 19 20 func isConnected(_ graph: [Int: Set<Int>], _ edge: [Int], _ source: Int, _ N: Int) -> Bool { 21 var graph = graph 22 graph[edge[0]]!.remove(edge[1]) 23 graph[edge[1]]!.remove(edge[0]) 24 var stack = [Int]() 25 var visited = Set<Int>() 26 stack.append(source) 27 while !stack.isEmpty { 28 let node = stack.popLast()! 29 visited.insert(node) 30 for edge in graph[node] ?? [] { 31 if !visited.contains(edge) { 32 stack.append(edge) 33 } 34 } 35 } 36 37 return visited.count == N 38 } 39 }
112ms
1 class Solution { 2 3 let MAX_EDGE_VAL = 1000 4 5 func findRedundantConnection(_ edges: [[Int]]) -> [Int] { 6 var graph = [Int: [Int]]() 7 8 for edge in edges { 9 let u = edge[0] 10 let v = edge[1] 11 var visited = Set<Int>() 12 if hasPath(&graph, &visited, u, v) { 13 return [u, v] 14 } 15 graph[u] = graph[u] ?? [Int]() 16 graph[u]!.append(v) 17 graph[v] = graph[v] ?? [Int]() 18 graph[v]!.append(u) 19 } 20 return [-1, -1] 21 } 22 23 public func hasPath(_ graph: inout [Int: [Int]], _ visited: inout Set<Int>, _ source: Int, _ target: Int) -> Bool { 24 if source == target { 25 return true 26 } 27 if !graph.keys.contains(source) || !graph.keys.contains(target) { 28 return false 29 } 30 visited.insert(source) 31 if let neighbers = graph[source] { 32 for neighber in neighbers { 33 if visited.contains(neighber) { 34 continue 35 } 36 if hasPath(&graph, &visited, neighber, target) { 37 return true 38 } 39 } 40 } 41 return false 42 } 43 }