并查集.md

并查集

并查集，在一些有N个元素的集合应用问题中，我们通常是在开始时让每个元素构成一个单元素的集合，然后按一定顺序将属于同一组的元素所在的集合合并，其间要反复查找一个元素在哪个集合中。这一类问题近几年来反复出现在信息学的国际国内赛题中，其特点是看似并不复杂，但数据量极大，若用正常的数据结构来描述的话，往往在空间上过大，计算机无法承受；即使在空间上勉强通过，运行的时间复杂度也极高，根本就不可能在比赛规定的运行时间（1～3秒）内计算出试题需要的结果，只能用并查集来描述。

并查集是一种树型的数据结构，用于处理一些不相交集合（Disjoint Sets）的合并及查询问题。常常在使用中以森林来表示。

案例

首先在地图上给你若干个城镇，这些城镇都可以看作点，然后告诉你哪些对城镇之间是有道路直接相连的。最后要解决的是整幅图的连通性问题。比如随意给你两个点，让你判断它们是否连通，或者问你整幅图一共有几个连通分支，也就是被分成了几个互相独立的块。像畅通工程这题，问还需要修几条路，实质就是求有几个连通分支。如果是1个连通分支，说明整幅图上的点都连起来了，不用再修路了；如果是2个连通分支，则只要再修1条路，从两个分支中各选一个点，把它们连起来，那么所有的点都是连起来的了；如果是3个连通分支，则只要再修两条路……

下面讲个一个小例子帮助理解

江湖上散落着各式各样的大侠，有上千个之多。他们没有什么正当职业，整天背着剑在外面走来走去，碰到和自己不是一路人的，就免不了要打一架。但大侠们有一个优点就是讲义气，绝对不打自己的朋友。而且他们信奉“朋友的朋友就是我的朋友”，只要是能通过朋友关系串联起来的，不管拐了多少个弯，都认为是自己人。这样一来，江湖上就形成了一个一个的帮派，通过两两之间的朋友关系串联起来。而不在同一个帮派的人，无论如何都无法通过朋友关系连起来，于是就可以放心往死了打。但是两个原本互不相识的人，如何判断是否属于一个朋友圈呢？

我们可以在每个朋友圈内推举出一个比较有名望的人，作为该圈子的代表人物。这样，每个圈子就可以这样命名“中国同胞队”美国同胞队”……两人只要互相对一下自己的队长是不是同一个人，就可以确定敌友关系了。

但是还有问题啊，大侠们只知道自己直接的朋友是谁，很多人压根就不认识队长抓狂要判断自己的队长是谁，只能漫无目的的通过朋友的朋友关系问下去：“你是不是队长？你是不是队长？”这样，想打一架得先问个几十年，饿都饿死了，受不了。这样一来，队长面子上也挂不住了，不仅效率太低，还有可能陷入无限循环中。于是队长下令，重新组队。队内所有人实行分等级制度，形成树状结构，我队长就是根节点，下面分别是二级队员、三级队员。每个人只要记住自己的上级是谁就行了。遇到判断敌友的时候，只要一层层向上问，直到最高层，就可以在短时间内确定队长是谁了。由于我们关心的只是两个人之间是否是一个帮派的，至于他们是如何通过朋友关系相关联的，以及每个圈子内部的结构是怎样的，甚至队长是谁，都不重要了。所以我们可以放任队长随意重新组队，只要不搞错敌友关系就好了。于是，门派产生了

内容转载自：并查集详解（超级简单有趣~~就学会了）

代码实现

并查集主要是要实现一下两个方法

• 1、isConnected(int p, int q) 两个元素是否有链接
• 2、unionElements(int p, int q) 合并两个元素

我们使用元素都是数组的简单实现一下

数组实现

    // 我们的第一版Union-Find本质就是一个数组
    private var ids:[Int] = Array()
    init(size:Int) {
        super.init()
        // 初始化, 每一个id[i]指向自己, 没有合并的元素
        for item in 0..<size {
        ids.append(item)
      }
    }
    
    // 查找元素p所对应的集合编号
    // O(1)复杂度
    func find(_ p:Int) -> Int {
       if p >= ids.count || p < 0 {
       fatalError("p is out of bound")
       }
      return ids[p]
    }   
    
    // 查看元素p和元素q是否所属一个集合
    // O(1)复杂度
    func isConnected(p:Int,q:Int) -> Bool {
      return find(p) == find(q)
    } 
    
    // 合并元素p和元素q所属的集合
    // O(n) 复杂度
    func unionElements(p:Int,q:Int) {
     let qId = find(q)
     let pId = find(p)
    
     if qId == pId {
      return
     }
    // 合并过程需要遍历一遍所有元素, 将两个元素的所属集合编号合并
    for (index,item) in ids.enumerated() {
      if (pId == item){
        ids[index] = qId
      }
     }
    }
  

数组实现

• 查看元素p和元素q是否所属一个集合的复杂度为O(1)
• 合并元素p和元素q所属的集合的复杂度为O(n)

第一种树

class UnionFind2: NSObject {
// 我们的第二版Union-Find, 使用一个数组构建一棵指向父节点的树
// parent[i]表示第一个元素所指向的父节点
private var parent:[Int] = Array()

init(size:Int) {
super.init()
// 初始化, 每一个parent[i]指向自己, 表示每一个元素自己自成一个集合
for item in 0..<size {
parent.append(item)
}
}

// 查找过程, 查找元素p所对应的集合编号
// O(h)复杂度, h为树的高度
func find(_ p:Int) -> Int {
if p >= parent.count || p < 0 {
fatalError("p is out of bound")
}
// 不断去查询自己的父亲节点, 直到到达根节点
// 根节点的特点: parent[p] == p
var root = p
while root != parent[root] {
root = parent[root]
}

return root
}

// 查看元素p和元素q是否所属一个集合
// O(h)复杂度, h为树的高度
func isConnected(p:Int,q:Int) -> Bool {
return find(p) == find(q)
}

// 合并元素p和元素q所属的集合
// O(h)复杂度, h为树的高度
func unionElements(p:Int,q:Int) {
let qRoot = find(q)
let pRoot = find(p)
if qRoot == pRoot {
return
}
parent[qRoot] = pRoot
}

}

这种树不做任何判断，直接替换

第二种树

class UnionFind3: NSObject {
// parent[i]表示第一个元素所指向的父节点
private var parent:[Int] = Array()
// 表示以i为根的集合中元素个数
private var sz:[Int] = Array()
init(size:Int) {
super.init()
// 初始化, 每一个parent[i]指向自己, 表示每一个元素自己自成一个集合
for item in 0..<size {
parent.append(item)
sz.append(1)
}
}


// 查找过程, 查找元素p所对应的集合编号
// O(h)复杂度, h为树的高度
func find(_ p:Int) -> Int {
if p >= parent.count || p < 0 {
fatalError("p is out of bound")
}
// 不断去查询自己的父亲节点, 直到到达根节点
// 根节点的特点: parent[p] == p
var root = p
while root != parent[root] {
root = parent[root]
}

return root
}

// 查看元素p和元素q是否所属一个集合
// O(h)复杂度, h为树的高度
func isConnected(p:Int,q:Int) -> Bool {
return find(p) == find(q)
}

// 合并元素p和元素q所属的集合
// O(h)复杂度, h为树的高度
func unionElements(p:Int,q:Int) {
let qRoot = find(q)
let pRoot = find(p)
if qRoot == pRoot {
return
}

// 根据两个元素所在树的元素个数不同判断合并方向
// 将元素个数少的集合合并到元素个数多的集合上
if sz[pRoot] < sz[qRoot] {
parent[pRoot] = qRoot
sz[qRoot] += sz[pRoot]
}else{
parent[qRoot] = pRoot;
sz[pRoot] += sz[qRoot];
}

}


}

添加了一个元素个数少的一方，添加到元素个数多的一方的判断

第三种树

class UnionFind4: NSObject {
// parent[i]表示第一个元素所指向的父节点
private var parent:[Int] = Array()
// rank[i]表示以i为根的集合所表示的树的层数
private var rank:[Int] = Array()

init(size:Int) {
super.init()
// 初始化, 每一个parent[i]指向自己, 表示每一个元素自己自成一个集合
for item in 0..<size {
parent.append(item)
rank.append(1)
}
}

// 查找过程, 查找元素p所对应的集合编号
// O(h)复杂度, h为树的高度
func find(_ p:Int) -> Int {
if p >= parent.count || p < 0 {
fatalError("p is out of bound")
}
// 不断去查询自己的父亲节点, 直到到达根节点
// 根节点的特点: parent[p] == p
var root = p
while root != parent[root] {
root = parent[root]
}

return root
}

// 查看元素p和元素q是否所属一个集合
// O(h)复杂度, h为树的高度
func isConnected(p:Int,q:Int) -> Bool {
return find(p) == find(q)
}

// 合并元素p和元素q所属的集合
// O(h)复杂度, h为树的高度
func unionElements(p:Int,q:Int) {
let qRoot = find(q)
let pRoot = find(p)
if qRoot == pRoot {
return
}
// 根据两个元素所在树的rank不同判断合并方向
// 将rank低的集合合并到rank高的集合上
if(rank[pRoot] < rank[qRoot]){
parent[pRoot] = qRoot;
}else if(rank[qRoot] < rank[pRoot]){
parent[qRoot] = pRoot;
}else{ // rank[pRoot] == rank[qRoot]
parent[pRoot] = qRoot;
rank[qRoot] += 1;   // 此时, 我维护rank的值
}

}

}

有根据元素个数判断，变成了层数判断