又名Union Find,是一种特殊的树结构，专门用于解决连接问题(Connectivity Problem)。注意6.4开始的代码才有实用性，6.2和6.3的效率都太低了.
和图论中的连通性问题是一样的，这里应该是图论中的连通性问题的提取和抽象。参考4.2 求每个连通分量里各自具体有哪些节点和4.3图论中实现地判断两个点的连通性
- 网络节点间的连接状态(用户网络、路由器网络等)
- 数学中的集合类实现(并查集中的并就是并集的意思，这里的含义就是当p、q两个节点连接到一起时，p、q所在的网路也就被并在了一起，两个网络合成了一个网络，里面的节点都是互通地)
void union(int p, int q):将两个元素连接起来，等效于p、q所在的网络群组并到了一起，我自己的实现叫unionElements()int find(int p):返回节点p所在的网络群组的id
boolean isConnected(int p, int q):p、q在网络中是否连通
find()方法的更快实现 O(1),但是Union操作效率较低 O(n) (因为p向q进行union时，需要改p所在网络的所有节点)
for (int i = 0; i < count; ++i) {
// 找到p所在的组了，为了把q加进来，所有=pID的id[i]改成qID即可，注意p也在这次循环修改的范围内了
if (id[i] == pID) {
id[i] = qID;
}
}ubion()方法的更快实现 O(logn), find()查询较慢 O(logn) ,综合比较下，Quick Union的实现更好，也确实是业内并查集的主流实现
核心原理是把pq所在的网络各自当成树，把两个点的union转化成两个树的根节点的union，这样union操作每次只需要操作一次就行，不需要处理p的所有节点，效率自然高了不少
/**
* 连接两个元素p和q
*/
public void unionElements(int p, int q) {
// 找到p元素对应的根
int pRoot = find(p);
int qRoot = find(q);
// 根元素相等说明两个元素已经在同一个并查集内了，是相互连接地了。直接返回
if (pRoot == qRoot) {
return;
}
// 不在一个并查集内的话，只需要把两个根节点连接起来即可
parent[pRoot] = qRoot;
}优化2：通过比较两个并查集的大小来决定pRoot连接qRoot, 还是qRoot连接pRoot(即谁是谁的父节点，元素少的并查集根节点连接元素多的并查集的根节点)
核心思想：p和q所在网络节点数在union时，将元素少的网络根节点 指向(union) 元素多的网络根节点，不再固定从p指向q
Union 9,4 的效率还行，9指向8，root节点连接后还算是比较均衡的一个树
但是Union 4,9时，因为根节点是8指向9，当进行后续的Union时，树已经成了一条线，在网上查找根节点时就会效率很低
基于size的优化的理解
◆问题 逻辑上，union 9, 4 与 union 4, 9 相同，但后者树更高—>花费的查找时间更多
◆解决 在作指向操作前进行判断——存储每个集合元素个数，判断集合大小（size），将元素少的集合的根节点指向多的
/**
* 连接两个元素p和q
*/
void unionElements(int p, int q) {
// 找到p元素对应的根
int pRoot = find(p);
int qRoot = find(q);
// 根元素相等说明两个元素已经在同一个并查集内了，是相互连接地了。直接返回
if (pRoot == qRoot) {
return;
}
// 不在一个并查集内的话，只需要把两个根节点连接起来即可
// 下面按照两个并并查集的大小决定谁连接谁(元素少地连接元素多地)
if (sz[pRoot] < sz[qRoot]) { // p所在的并查集元素数小于q所在的并查集元素数，p指向q
// p所在的并查集连接q所在的并查集
parent[pRoot] = qRoot;
// 把q所在的并查集的元素书加上p所在的并查集的元素数
sz[qRoot] += sz[pRoot];
} else { // p所在的并查集元素数大于q所在的并查集元素数,q指向p
// q所在的并查集连接p所在的并查集
parent[qRoot] = pRoot;
// 把p所在的并查集的元素书加上q所在的并查集的元素数
sz[pRoot] += sz[qRoot];
}
}优化3：按照两个并查集的层数来判断谁和谁连接，这样更准确，因为遍历的时候就是逐层遍历
优化4：find操作之前先把层数过多的并查集进行压缩，通过把尽量多的节点指向根节点来减少层数