【LSP】并查集（UnionFind）技巧总结
http://cdn.u1.huluxia.com/g4/M01/6E/53/rBAAdl94P8qAHWbsAACt4WdlvYs974.jpg
什么是并查集
在计算机科学中，并查集是一种树型的数据结构，用于处理一些不交集（Disjoint Sets）的合并及查询问题。有一个联合-查找算法（Union-find Algorithm）定义了两个用于此数据结构的操作：
Find：确定元素属于哪一个子集。它可以被用来确定两个元素是否属于同一子集。
Union：将两个子集合并成同一个集合。
由于支持这两种操作，一个不相交集也常被称为联合-查找数据结构（Union-find Data Structure）或合并-查找集合（Merge-find Set）。
并查集可以解决什么问题
组团、配对
图的连通性问题
集合的个数
集合中元素的个数
算法模板http://cdn.u1.huluxia.com/g4/M01/6E/53/rBAAdl94P8qAL4M6AAN-ySPgNR8392.jpg
实例
547. 朋友圈http://cdn.u1.huluxia.com/g4/M01/6E/53/rBAAdl94P8uAARNnAAB6gKe5x_8146.png
题目分析：
题目求的是有多少个朋友圈，也就是求有集合个数，可用并查集解决。
两重遍历所有学生，判断俩俩是否为朋友，如为朋友将加入到集合中。这里可以通过遍历二维矩阵的右半边即可，可降低遍历数量，从而降低时间复杂度。
代码实现：http://cdn.u1.huluxia.com/g4/M01/6E/53/rBAAdl94P8yAZFAzAADa0r0GSIE365.jpg
复杂度分析：
时间复杂度：O(n2)O(n2)。两重遍历用时 O(n2)O(n2) ，uf.union 和 uf.find 的时间复杂度为 O(1)O(1) ，所以总的时间复杂度为 O(n2)O(n2)。
空间复杂度：O(n)O(n)。需要一个 O(n)O(n) 大小的空间。
200. 岛屿数量
http://cdn.u1.huluxia.com/g4/M01/6E/53/rBAAdl94P8yAKPZJAABdju4TDZY319.png
题目分析：
题目求的是岛屿数量，即集合个数，可用并查集解决。
题目可抽象为遍历所有网格 (i, j)，如果是陆地（(i, j) == '1'），则把其右边的陆地（(i+1, j) == '1'）和下边的陆地（(i, j+1) == '1'）合并到一起；如是水（(i, j) == '0'），则把其合并到一个哨兵集合里。最后返回 集合个数 - 1。
注：这里关键是对于水的处理，把其合并到一个哨兵集合里，让水不会单独存在，从而干扰岛屿个数的判断。
代码实现：http://cdn.u1.huluxia.com/g4/M01/6E/53/rBAAdl94P82AXAxwAAROd8B-UyE382.jpg
总结
要熟练掌握并查集的模板，要能够快速写出来。
要掌握并查集的应用场景。例如组团、配对、图的连通性问题、集合个数、集合中元素的个数等。
对于二维的问题转一维解决，例如 200. 岛屿数量 和 130. 被围绕的区域。
找出元素间的“配对”关系是解决问题的关键。例如二维数组，找当前位置与其右和其下配对。例如 200. 岛屿数量 和 130. 被围绕的区域。 鼎力支持！！ LZ敢整点更有创意的不？兄弟们等着围观捏~ 锄禾日当午，发帖真辛苦。谁知坛中餐，帖帖皆辛苦！ 占位编辑 顶顶更健康 介是神马？！！ LZ是天才，坚定完毕
页:
[1]