朋友的朋友就是我的朋友
什么是查并集？
查并集是一种数据结构，用于跟踪不相连子集中的元素，查并集有两个重要操作：
搜索（查）：决定元素位于哪一个子集中，例如在下式中，$5\in S_2$。
联合（并）：将两个子集合并为一个更大的子集
从查并集的定义中可以看出，其中的各个子集是相互独立的，可以将每一个子集视为一个独立的组织，例如按势力将武侠小说中的人物进行划分（丐帮和峨眉是两个独立门派，二者之间没有交集）。例如下式中，$S_1$与$S_2$是相互独立的。
graph LR
subgraph S1
node1((1))
node2((2))
node3((3))
node4((4))
end
subgraph S2
node5((5))
node6((6))
node7((7))
node8((8))
end
node1---node2
node2---node3
node3---node4
node5---node6
node6---node7
node7---node8
联合操作示意如下，例如我们要联合节点$4$和$8$，即union(4,8)，那么得到的结果为$S_1\cup S_2 ={1,2,3,4,5,6,7,8}$，即联合的结果就是将两个不同的集合合并
graph LR
subgraph S1\cap S2
node1((1))
node2((2))
node3((3))
node4((4))
node5((5))
node6((6))
node7((7))
node8((8))
end
node1---node2
node2---node3
node3---node4
node5---node6
node6---node7
node7---node8
node8---node4
查并集基本操作及实现3
基本操作
从查并集的名字可以看出，查并集主要操作有两个：即查和并。当然，为了判断是否连通，我们还需判断两个点是否在同一连通区域内部，以及某个节点是否在查并集中。
init(int n): 初始化并查集，将每个节点的父节点设置为自身节点。find(int m)：这是并查集的基本操作，查找m的根节点。union(int m,int n)：合并m,n两个点所在的连通区域。isConnected(int m,int n)：判断m,n两个点是否在一个连通区域。isContained(int node)：判断是否在查并集中getMaxSize()：获得查并集中最大子集的规模
初始化
令$P={p_1,}$
基本操作的流程和代码如下：
graph TB
start(Start)
judge1{"parent[node] == node?"}
return["return node"]
End("end")
state1["parent[node] = parent[parent[node]]"]
start-->judge1
judge1-->return
1 | class UnionFind { |
graph TB
subgraph find
A((root))
B((node1))
C((node2))
D((node3))
E((node4))
A---B
B---C
C---D
B---E
end
subgraph union
end
subgraph isConnected
end
实现
数组实现查并集
查并集应用
解决连通性问题
查并集常用于解决连通性问题，即将一个图中的连通部分进行划分。当判断图中两点是否存在路径时，可以根据判断他们是否在一个连通区域内。
解决邻接问题
在有些问题中，可能出现诸如找到所有连续的整数构成的子集，这种情况下可以把问题转换为一个查并集问题，假设当前正在寻找的对象为v，如果nums中存在v+1或者v-1，我们就可以把v和v+1（v-1）归并至一个集合内部。
例题
给定一个未排序的整数数组，找出最长连续序列的长度。要求算法的时间复杂度为 O(n)。
输入: [100, 4, 200, 1, 3, 2]
输出: 4
解释: 最长连续序列是 [1, 2, 3, 4]。它的长度为 4。
思路
我们可以构造一个查并集，并利用map进行索引，如果v的相邻数存在，那么我们对v和v的相邻数进行union操作，需要注意的是数组中可能存在重复元素，这种情况下我们需要一个visited集合，如果数已经出现，直接跳过即可。
关键代码
1 | //在union中，当合并两个set时，我们可以顺手更新set的规模 |
判断无向图是否成环
给定集合如下：
其构成的无向图为（边上为序号）：
graph TB
node1((1))
node2((2))
node3((3))
node4((4))
node5((5))
node6((6))
node7((7))
node8((8))
node1--7---node3
node1--1---node2
node2--5---node4
node3--2---node4
node2--6---node5
node5--9---node7
node5--3---node6
node6--8---node8
node7--4---node8
在上图中，我们寻找circle的过程如下：
找到第一条边的Union，即union(1,2)，我们的集合变为
重复上述步骤：
当从第五条边开始，我们开始进行集合间的合并：
而当我们处理第七条边时，发现第七条边的两个node均在$S_6$中，说明出现了环。因为一开始每条边都是独立的set，所以当出现一个边的两个节点在同一个集合中，第一说明这两个节点是相连的，第二说明这两个节点之 前已经通过其他边连在一起，所以会有环。
我们再用图的步骤描述上面的过程，访问前四条边后，我们找到了四个集合：
graph BT
subgraph set1
node1((1))
node2((2))
end
subgraph set2
node3((3))
node4((4))
end
subgraph set3
node5((5))
node6((6))
end
subgraph set4
node7((7))
node8((8))
end
node2-->node1
node4-->node3
node6-->node5
node8-->node7
我们令union(u,v)中，$u$为父节点，$v$为子节点，当我们进行union(2,4)即处理第5条边的操作后，图变为：
graph BT
subgraph set1
node1((1))
node2((2))
node3((3))
node4((4))
end
subgraph set2
node5((5))
node6((6))
end
subgraph set3
node7((7))
node8((8))
end
node2-->node1
node4-->node3
node3-->node1
node6-->node5
node8-->node7
即将4所在的集合的父节点3作为2所在集合的父节点1的子节点，同理，处理第6条边结果如下：
graph BT
subgraph set1
node1((1))
node2((2))
node3((3))
node4((4))
node5((5))
node6((6))
end
subgraph set2
node7((7))
node8((8))
end
node2-->node1
node4-->node3
node3-->node1
node5-->node1
node6-->node5
node8-->node7
伪代码如下：
1 | for each unvisited edge (u,v) in set E{ |
例题
本题的宗旨是判断查并集内环和独立子集的个数，比较简单。
查并集优化
平衡性优化
当查并集中两个集合进行合并时，我们希望规模较小的集合接到规模大的集合的下面，这样可以避免树头重脚轻，使树更加平衡，此时我们需要一个额外的size数组，对每个集合的规模进行统计，代码如下：
1 | void union(int node1, int node2) { |
路径压缩优化
路径压缩优化是针对find操作的优化，通过路径压缩，可以进一步降低搜索树的深度，提高查询效率。经过深度的路径压缩，查询效率甚至可以接近O(1)。路径压缩的基本操作就是在查找时将树深度不断降低，代码如下：
1 | int find(int node) { |