抬头仰望星空,是否能发现自己的渺小。

伪斜杠青年

人们总是混淆了欲望和理想

52 | 理论讲解:并查集

并查集 (union & find) 是一种树型的数据结构,⽤于处理⼀些不交集(Disjoint Sets)的合并及查询问题。

Find:确定元素属于哪一个⼦集。它可以被用来确定两个元素是否属于同一⼦集。

Union:将两个⼦集合并成同⼀个集合。

直观表示:

数据结构:

伪代码:
最后的 xRoot.parent = yRoot,也可改为yRoot.parent = xRoot,因为目的只是为了合并

在生活中的例子

  1. 通过小弟找⽼大
  2. 帮派识别

两种优化方式

按秩合并:wiki
合并时将元素所在深度小的集合合并到元素所在深度大的集合。

伪代码:

路径压缩:wiki
找到最久远的祖先时“顺便”把它的子孙直接连接到它上面

java 代码:

class QuickUnionUF(N: Int) {
val parent = IntArray(N) { it }
var count=N

fun findRoot(p: Int): Int {
var root = p
while (root != parent[root]) {
root = parent[root]
}
//路径压缩
var r = p
while (r != parent[r]) {
r = parent[r].also {
parent[r] = root
}
}
return root
}

fun connected(p: Int, q: Int): Boolean {
return findRoot(p) == findRoot(q)
}

fun union(p: Int, q: Int) {
val qRoot = findRoot(q)
val pRoot = findRoot(p)
//任选一句均可
parent[qRoot] = pRoot
//roots[pRoot]=qRoot
count--
}

}

实战题目:

200. 岛屿数量

547. 朋友圈

推荐文章:数据结构与算法:学习并查集


0条评论

发表评论