剑指 Offer II 116. 省份数量

并查集。感觉用quick find会比较好点

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 findCircleNum(_ isConnected: [[Int]]) -> Int {
        
    let len = isConnected.count
    let uf = MyUnionFind(len)
        for i in 0..<len {
            for j in 0..<len {
                if i == j {
                    continue
                }
                if isConnected[i][j] == 1 {
                    uf.union(i,j)
                }
            }
            
        }
        var dict = Set<Int>()
        for i in uf.parents {
            dict.insert(uf.find(i))
        }
        return dict.count
    }
}