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 }

 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 }

 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 }

 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 }

  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 }

 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 }

 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 }