[Swift]LeetCode684. 冗余连接 | Redundant Connection
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? 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? 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,[3,4],5]] Output: [1,4] Explanation: The given undirected graph will be like this: 5 - 1 - 2 | | 4 - 3? Note:
Update (2017-09-26): 在本问题中,树指的是一个连通且无环的无向图。 输入一个图,该图由一个有着N个节点 (节点值不重复1,N) 的树及一条附加的边构成。附加的边的两个顶点包含在1到N中间,这条附加的边不属于树中已存在的边。 结果图是一个以 返回一条可以删去的边,使得结果图是一个有着N个节点的树。如果有多个答案,则返回二维数组中最后出现的边。答案边? 示例 1: 输入: [[1,3]] 输出: [2,3] 解释: 给定的无向图为: 1 / 2 - 3 示例 2: 输入: [[1,5]] 输出: [1,4] 解释: 给定的无向图为: 5 - 1 - 2 | | 4 - 3 注意:
更新(2017-09-26):
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.1) ) 37 } 38 } 39 } 40 41 return _edges.last! 42 } 43 } 44 45 46 47 48 49 public struct Heap<T> { 50 51 /** The array that stores the heap‘s nodes. */ 52 var nodes = [T]() 53 54 /** 55 * Determines how to compare two nodes in the heap. 56 * Use ‘>‘ for a max-heap or ‘<‘ for a min-heap, 57 * or provide a comparing method if the heap is made 58 * of custom elements,for example tuples. 59 */ 60 private var orderCriteria: (T,T) -> Bool 61 62 /** 63 * Creates an empty heap. 64 * The sort function determines whether this is a min-heap or max-heap. 65 * For comparable data types,> makes a max-heap,< makes a min-heap. 66 */ 67 public init(sort: @escaping (T,T) -> Bool) { 68 self.orderCriteria = sort 69 } 70 71 /** 72 * Creates a heap from an array. The order of the array does not matter; 73 * the elements are inserted into the heap in the order determined by the 74 * sort function. For comparable data types,‘>‘ makes a max-heap, 75 * ‘<‘ makes a min-heap. 76 */ 77 public init(array: [T],sort: @escaping (T,T) -> Bool) { 78 self.orderCriteria = sort 79 configureHeap(from: array) 80 } 81 82 /** 83 * Configures the max-heap or min-heap from an array,in a bottom-up manner. 84 * Performance: This runs pretty much in O(n). 85 */ 86 private mutating func configureHeap(from array: [T]) { 87 nodes = array 88 for i in stride(from: (nodes.count/2-1),through: 0,by: -1) { 89 shiftDown(i) 90 } 91 } 92 93 public var isEmpty: Bool { 94 return nodes.isEmpty 95 } 96 97 public var count: Int { 98 return nodes.count 99 } 100 101 /** 102 * Returns the index of the parent of the element at index i. 103 * The element at index 0 is the root of the tree and has no parent. 104 */ 105 @inline(__always) internal func parentIndex(ofIndex i: Int) -> Int { 106 return (i - 1) / 2 107 } 108 109 /** 110 * Returns the index of the left child of the element at index i. 111 * Note that this index can be greater than the heap size,in which case 112 * there is no left child. 113 */ 114 @inline(__always) internal func leftChildIndex(ofIndex i: Int) -> Int { 115 return 2*i + 1 116 } 117 118 /** 119 * Returns the index of the right child of the element at index i. 120 * Note that this index can be greater than the heap size,in which case 121 * there is no right child. 122 */ 123 @inline(__always) internal func rightChildIndex(ofIndex i: Int) -> Int { 124 return 2*i + 2 125 } 126 127 /** 128 * Returns the maximum value in the heap (for a max-heap) or the minimum 129 * value (for a min-heap). 130 */ 131 public func peek() -> T? { 132 return nodes.first 133 } 134 135 /** 136 * Adds a new value to the heap. This reorders the heap so that the max-heap 137 * or min-heap property still holds. Performance: O(log n). 138 */ 139 public mutating func insert(_ value: T) { 140 nodes.append(value) 141 shiftUp(nodes.count - 1) 142 } 143 144 /** 145 * Adds a sequence of values to the heap. This reorders the heap so that 146 * the max-heap or min-heap property still holds. Performance: O(log n). 147 */ 148 public mutating func insert<S: Sequence>(_ sequence: S) where S.Iterator.Element == T { 149 for value in sequence { 150 insert(value) 151 } 152 } 153 154 /** 155 * Allows you to change an element. This reorders the heap so that 156 * the max-heap or min-heap property still holds. 157 */ 158 public mutating func replace(index i: Int,value: T) { 159 guard i < nodes.count else { return } 160 161 remove(at: i) 162 insert(value) 163 } 164 165 /** 166 * Removes the root node from the heap. For a max-heap,this is the maximum 167 * value; for a min-heap it is the minimum value. Performance: O(log n). 168 */ 169 @discardableResult public mutating func remove() -> T? { 170 guard !nodes.isEmpty else { return nil } 171 172 if nodes.count == 1 { 173 return nodes.removeLast() 174 } else { 175 // Use the last node to replace the first one,then fix the heap by 176 // shifting this new first node into its proper position. 177 let value = nodes[0] 178 nodes[0] = nodes.removeLast() 179 shiftDown(0) 180 return value 181 } 182 } 183 184 /** 185 * Removes an arbitrary node from the heap. Performance: O(log n). 186 * Note that you need to know the node‘s index. 187 */ 188 @discardableResult public mutating func remove(at index: Int) -> T? { 189 guard index < nodes.count else { return nil } 190 191 let size = nodes.count - 1 192 if index != size { 193 nodes.swapAt(index,size) 194 shiftDown(from: index,until: size) 195 shiftUp(index) 196 } 197 return nodes.removeLast() 198 } 199 200 /** 201 * Takes a child node and looks at its parents; if a parent is not larger 202 * (max-heap) or not smaller (min-heap) than the child,we exchange them. 203 */ 204 internal mutating func shiftUp(_ index: Int) { 205 var childIndex = index 206 let child = nodes[childIndex] 207 var parentIndex = self.parentIndex(ofIndex: childIndex) 208 209 while childIndex > 0 && orderCriteria(child,nodes[parentIndex]) { 210 nodes[childIndex] = nodes[parentIndex] 211 childIndex = parentIndex 212 parentIndex = self.parentIndex(ofIndex: childIndex) 213 } 214 215 nodes[childIndex] = child 216 } 217 218 /** 219 * Looks at a parent node and makes sure it is still larger (max-heap) or 220 * smaller (min-heap) than its childeren. 221 */ 222 internal mutating func shiftDown(from index: Int,until endIndex: Int) { 223 let leftChildIndex = self.leftChildIndex(ofIndex: index) 224 let rightChildIndex = leftChildIndex + 1 225 226 // Figure out which comes first if we order them by the sort function: 227 // the parent,the left child,or the right child. If the parent comes 228 // first,we‘re done. If not,that element is out-of-place and we make 229 // it "float down" the tree until the heap property is restored. 230 var first = index 231 if leftChildIndex < endIndex && orderCriteria(nodes[leftChildIndex],nodes[first]) { 232 first = leftChildIndex 233 } 234 if rightChildIndex < endIndex && orderCriteria(nodes[rightChildIndex],nodes[first]) { 235 first = rightChildIndex 236 } 237 if first == index { return } 238 239 nodes.swapAt(index,first) 240 shiftDown(from: first,until: endIndex) 241 } 242 243 internal mutating func shiftDown(_ index: Int) { 244 shiftDown(from: index,until: nodes.count) 245 } 246 247 } 248 249 // MARK: - Searching 250 extension Heap where T: Equatable { 251 252 /** Get the index of a node in the heap. Performance: O(n). */ 253 public func index(of node: T) -> Int? { 254 return nodes.index(where: { $0 == node }) 255 } 256 257 /** Removes the first occurrence of a node from the heap. Performance: O(n log n). */ 258 @discardableResult public mutating func remove(node: T) -> T? { 259 if let index = index(of: node) { 260 return remove(at: index) 261 } 262 return nil 263 } 264 } 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>,_ 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,neighber,target) { 37 return true 38 } 39 } 40 } 41 return false 42 } 43 } (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |