一、啥是并查集
1、解释
看下维基百科的解释
啥？在说啥，看不懂？那说人话吧
艰深的说，并查集是一种数据结构，指在一些有N个元素的汇合利用问题中，通常在开始时让每个元素形成一个单元素的汇合，而后按肯定程序将属于同一组的元素所在的汇合合并，其间要重复查找一个元素在哪个汇合中。用于解决一些不相交汇合的合并及查问问题。
2、有啥劣势
在足够多的合并和查问操作后，均摊下来单次的查问工夫复杂度是O(1)。
3、作用
解决相似图的连通性问题大量应用并查集。
二、次要操作
1、初始化：把每个点所在汇合初始化为其本身
通常来说，这个步骤在每次应用该数据结构时只须要执行一次，无论何种实现形式，工夫复杂度均为O(N)。
2、查找：查找元素所在的汇合，即此汇合的代表节点——根节点
3、合并：将两个元素所在的汇合合并为一个汇合。汇合小的连到汇合大的
通常来说，合并之前，应先判断两个元素是否属于同一汇合，这可用下面的“查找”操作实现。
三、门路优化压缩
1、思维：每次查找的时候，如果门路较长，则批改信息，以便下次查找的时候速度更快。
2、实现：第一步，找到根结点；第二步，批改查找门路上的所有节点，将它们都指向根结点。
为啥最初均摊的工夫复杂度是O(1)？
门路优化压缩是要害
因为每次在查找时，都会把此门路上所有的节点从新全副间接连到根节点上，当前再查找时都是一步到位，一步就找到了根节点，除了查找根节点以外的操作自身就是O(1)，而一个门路上从新调整的操作只会执行一次，所以最初均摊下来的工夫复杂度是O(1)。
对于工夫复杂度O(1)的证实
并查集最早由Bernard A. Galler和Michael J. Fischer于1964年提出，然而直到Fredman 和 Saks 在 1989 年才证实了任何并查集都须要O(1)的均摊工夫来实现每次操作，25年才证实实现。
四、外围办法
/** * @author Java和算法学习：周一 */public static class UnionFind<V> { // 用户输出的V对应外部的Node<V> public HashMap<V, Node<V>> nodes; // Node<V>的父亲是谁 public HashMap<Node<V>, Node<V>> parents; // Node<V>所在汇合的大小（只有汇合的代表节点<能够了解为头节点>才会放到sizeMap中） public HashMap<Node<V>, Integer> sizeMap; // 初始化时把用户给定的数据全副放到各个Map中 public UnionFind(List<V> values) { nodes = new HashMap<>(); parents = new HashMap<>(); sizeMap = new HashMap<>(); for (V current : values) { Node<V> node = new Node<>(current); nodes.put(current, node); // 初始化时node的父亲是本人 parents.put(node, node); // 初始化时node的size是1 sizeMap.put(node, 1); } }}1、查找节点所在汇合的代表节点
/** * 找到指定节点所在的代表节点 * * @author Java和算法学习：周一 */public Node<V> findHead(Node<V> node) { Node<V> current = node; Stack<Node<V>> stack = new Stack<>(); // 以后节点的父节点不是本人，阐明还没找到最顶 while (current != parents.get(current)) { stack.push(current); current = parents.get(current); } // 优化：批改查找门路上的所有节点，将它们都指向根结点 while (!stack.isEmpty()) { parents.put(stack.pop(), current); } return current;}2、isSameSet(V a, V b)
判断a、b所代表的两个汇合是否在同一个汇合中
/** * 判断两个节点所在汇合是不是同一个汇合 * * @author Java和算法学习：周一 */public boolean isSameSet(V a, V b) { return findHead(nodes.get(a)) == findHead(nodes.get(b));}3、union(V a, V b)
将a、b所代表的两个汇合合并为一个汇合
/** * 将两个节点所在汇合合并为一个汇合 * * @author Java和算法学习：周一 */public void union(V a, V b) { Node<V> aHead = findHead(nodes.get(a)); Node<V> bHead = findHead(nodes.get(b)); if (aHead != bHead) { // 阐明a、b所在汇合不是同一个汇合 int aSize = sizeMap.get(aHead); int bSize = sizeMap.get(bHead); // 找到size更大的汇合 Node<V> big = aSize >= bSize ? aHead : bHead; Node<V> small = big == aHead ? bHead : aHead; // 小的连到大的下面（这也是一个优化） parents.put(small, big); // 从新调整big所在汇合的size sizeMap.put(big, aSize + bSize); // small所在汇合曾经连到big上，从sizeMap中移除 sizeMap.remove(small); }}所有代码地址：https://github.com/monday-pro/algorithm-study/blob/master/src/basic/unionfind/TheUnionFind.java
五、省份数量问题
1、题目形容
LeetCode547
https://leetcode-cn.com/probl...
有 n 个城市，其中一些彼此相连，另一些没有相连。如果城市 a 与城市 b 间接相连，且城市 b 与城市 c 间接相连，那么城市 a 与城市 c 间接相连。
省份 是一组间接或间接相连的城市，组内不含其余没有相连的城市。
给你一个 n x n 的矩阵 isConnected ，其中 isConnected[i][j] = 1 示意第 i 个城市和第 j 个城市间接相连，而 isConnected[i][j] = 0 示意二者不间接相连。
返回矩阵中 省份 的数量。
2、示例
输出：isConnected = [[1,1,0],[1,1,0],[0,0,1]]
[1, 1, 0]
[1, 1, 0]
[0, 0, 1]
输入：2
3、思路
如果晓得应用并查集来求解，这题就瓜熟蒂落了，挨个将相连的城市应用并查汇合并到一起，最初求并查集中汇合的数量就是省份的数量了。相当于并查集就能够当一个黑盒来应用了。
4、代码
为了优化代码的执行工夫，将最后由Map示意的汇合采纳一维数组来示意。
/** * @author Java和算法学习：周一 */public int findCircleNum(int[][] isConnected) { int length = isConnected.length; UnionFind unionFind = new UnionFind(length); // 因为整个 n*n 的二维矩阵是对于对角线对称的，而本人和本人是相连的，即对角线都是1，所以只需遍历一侧即可 // 咱们遍历的是右上方的数据 for (int i = 0; i < length; i++) { for (int j = i + 1; j < length; j++) { if (isConnected[i][j] == 1) { unionFind.union(i, j); } } } return unionFind.getSet();}所有代码地址：https://github.com/monday-pro/algorithm-study/blob/master/src/basic/unionfind/FindCircleNum.java