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.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 }

 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>, _ 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 }