并查集 swift

都是整数的话

import Foundation
class UnionFind {
    
    private var parents:[Int]
    //基于rank的优化
    private var ranks:[Int]
    
    init(_ capacity:Int){
        parents = Array.init(repeating: -1, count: capacity)
        ranks = Array.init(repeating: 1, count: capacity)
    }

    func find(_ v:Int) -> Int {
        
        checkRange(v)
        //路径压缩
//        if(parents[v] != -1){
//            parents[v] = find(v)
//        }
//        return parents[v]
        //路径分裂
//        var temp = v
//        while temp != -1 {
//            let p = parents[v]
//            parents[temp] = parents[parents[temp]]
//            temp = p
//        }
//        return temp
//        路径减半
            var temp = v
             while temp != -1 {
                 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
        }
        //基于rank的优化
        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 checkRange(_ v:Int){
        
        if v < 0 || v > parents.count {
            fatalError("下标越界了")
        }
        
    }

}

通用并查集

import Foundation


public class UnionNode<T: Hashable> : Hashable {
    public static func == (lhs: UnionNode<T>, rhs: UnionNode<T>) -> Bool {
        return lhs.value == rhs.value
    }
    public func hash(into hasher: inout Hasher) {
        hasher.combine(value)
        hasher.combine(parent)
        hasher.combine(rank)
    }
    
    
    var value:T
    var parent :UnionNode<T>?
    var rank = 1
    init(_ v:T){
        value = v
        parent = self
    }
    
    
    
}




class QuickUnion<T: Hashable> {
    
    private var map = [T:UnionNode<T>]()
    
    //创建集合
    func makeSet(_ v:T){
        //避免重复创建添加
        if let _ = map[v] {
           return
        }
        //key是student 值是对应节点
        map[v] = UnionNode(v)
    
    }
    private func findNode(_ v:T)-> UnionNode<T>? {
        
        if var node = map[v] {
            
            //路径减半
            while node != node.parent {
                node.parent = node.parent?.parent
                node = node.parent!
            }
            return node

        }
        //找不到的话返回nil
        return nil
        
    }
    //找到节点对应的值
    func find(_ v:T) -> T? {
        
        let node = findNode(v)
        return node == nil ? nil : node?.value
    }
    
    func union(_ v1:T,_ v2:T){
        let p1 = findNode(v1)
        let p2 = findNode(v2)
        if p1 == nil || p2 == nil {
            return
        }
        if p1 == p2 {
            return
        }
        //基于rank的优化
        let r1 = p1!.rank
        let r2 = p2!.rank
        if r1 < r2 {
            p1?.parent = p2
                
        }else if r1 > r2{
            p2?.parent = p1
        }else {
            p1?.parent = p2
            p2?.rank += 1
        }
        
    }
    
    
    
    func isSame(_ v1:T, _ v2:T) -> Bool{
        
        return find(v1) == find(v2)
        
    }
    
  
    
    
    
    
    
    
    
    
}

student类

import Foundation
class Student : Hashable{
    private var age : Int
    private var name : String
    init(_ age:Int,_ name:String){
        
        self.age = age
        self.name = name
    }
    func hash(into hasher: inout Hasher) {
        hasher.combine(age)
        hasher.combine(name)
    }
    static func == (lhs: Student, rhs: Student) -> Bool {
        return lhs === rhs
    }
    
}

测试代码

   let uf = QuickUnion<Student>()
        let v1 = Student(10,"小明")
        let v2 = Student(20,"小芳")
        let v3 = Student(30,"小红")
        let v4 = Student(40,"小蓝")
        uf.makeSet(v1)
        uf.makeSet(v2)
        uf.makeSet(v3)
        uf.makeSet(v4)
        uf.union(v1,v2)
        uf.union(v3,v4)

        print(uf.isSame(v1,v2))
        print(uf.isSame(v3,v2))
        print(uf.isSame(v3,v4))
   //true
   //false
   //true