steven_lv-20180819.md

ARTS Week Eight

Algorithm

Union-Find (disjoint-set data structure)

• 用树表示集合，由一系列不�相交集合组成，也就是由许多棵树组成
• 每棵树的元素都属于一个集合, ��所以该数据结构其实是维护了多棵树组成的森林
• 三个基本操作:
  • find(x): 找到 x 所在树的树根
  • unionSetsContaining(x, and: y): 合并两个集合成为一棵树
  • addSetWith(x): 新增一个只有 x 元素的子集合
• 优化: 在查找 root 节点的时候压缩路径

  public struct UnionFind<T:Hashable> {
    private(set) var index: [T: Int] = [T:Int]()
    private(set) var parent: [Int] = [Int]()
    private(set) var size: [Int] = [Int]()
    
    public init() {}
    
    public mutating func addSetWith(_ element: T) {
        index[element] = parent.count
        parent.append(parent.count)
        size.append(1)
    }

    // Find(x)
    public mutating func setOf(_ element: T) -> Int? {
        if let indexOfElement = index[element] {
            return setByIndex(indexOfElement)
        } else {
            return nil
        }
    }

    // path compress
    private mutating func setByIndex(_ index: Int) -> Int {
//        if parent[index] == index {  // 1
//            return index
//        } else {
//            parent[index] = setByIndex(parent[index])  // 2
//            return parent[index]       // 3
//        }
        if parent[index] != index {
            parent[index] = setByIndex(parent[index])
        }
        return parent[index]
    }
    
    public mutating func unionSetsContaining(_ firstSetElement: T, and secondElement: T) {
        if let firstSet = setOf(firstSetElement), let secondSet = setOf(secondElement) {
            if size[firstSet] < size[secondSet] {
                parent[firstSet] = secondSet
                size[secondSet] += size[firstSet]
            } else {
                parent[secondSet] = firstSet
                size[firstSet] += size[secondSet]
            }
        }
    }
    
    public mutating func inSameSet(_ firstElement: T, and secondElement: T) -> Bool {
        if let firstSet = setOf(firstElement), let secondSet = setOf(secondElement) {
            return firstSet == secondSet
        } else {
            return false
        }
    }
  }