剑指 Offer II 118. 多余的边

并查集

class Solution {
class MyUnionFind {
    var parents = [Int]()
    var ranks : [Int]
    
    init(_ capacity:Int){
        
        ranks = Array.init(repeating: 1, count: capacity)
        for i in 0..<capacity {
            parents.append(i)
        }

    }
    
    func find(_ v:Int)-> Int{
    
        var temp = v
        //路径减半
        while parents[temp] != temp {
            parents[temp] = parents[parents[temp]]
            temp = parents[temp]
        }
        return temp
    }
    
    func union(_ v1:Int,_ v2:Int){
        
        let p1 = find(v1)
        let p2 = find(v2)
        if p1 == p2 {
            return
        }
        let r1 = ranks[p1]
        let r2 = ranks[p2]
        if r1 < r2 {
            parents[p1] = p2
        }else if r1 > r2 {
            parents[p2] = p1
        }else {
            parents[p1] = p2
            ranks[p2] += 1
        }
        
    }
    func isSame(_ v1:Int,_ v2:Int)-> Bool{
        return find(v1) == find(v2)
        
    }
    
}


    func findRedundantConnection(_ edges: [[Int]]) -> [Int] {
           
        let len = edges.count
        let uf = MyUnionFind(len + 1)
        for e in edges {
            let v1 = e[0] ,v2 = e[1]
            if !uf.isSame(v1, v2) {
                uf.union(v1, v2)
            }else{
                return e
            }
        }
      
        return []
    
    }
}