一、啥是并查集
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
5、LeetCode 测试