并查集

并查集：快速合并两个连通块以及快速判断两个元素是否在同一连通块中。
find(x)：返回x的根节点，注意递归和回溯时的操作以及路径压缩

1.AcWing 528. 奶酪

法一：并查集

思路：
1.先将上表面的奶酪空洞（终点）以及下表面的奶酪空洞（起点）编号存入两个向量a,b中
2.双重循环枚举起点和终点，将所有能连通的点用并查集合并（dis(p1,p2)*dis(p1,p2)<=4*r*r既能合并）
3.枚举a中的点和b中的点，a中任意一点与b中任意一点在同一个连通块中则老鼠可以到达上表面

点击查看代码

2.AcWing 1250. 格子游戏

法一：并查集

思路：
1.将二维的n*n个点的坐标(x,y)（{0,0},{0,1},...）线性映射为编号a（0,1,...）
2.行：x=a/n 列：y=a%n 编号：a=x*n+y
3.用并查集快速连线（合并），已经存在同一连通块后再连线（合并）必成环

点击查看代码

3.AcWing 2069. 网络分析

法一：并查集

思路：
1.一个节点的信息量为当前结点到根节点所有的信息量之和，故仅需根节点增加信息量即可

2.a,b合并时，为保证信息量不多计算，先执行val[a]-=val[b]，再合并p[find(a)]=find(b)

3.路径压缩：先递归到根节点，回溯时因为（根节点和一级节点）无需叠加信息，故直接返回p[x]，
其他节点回溯时除根节点的信息量都将叠加回当前结点，且当前结点改为指向根节点

4.根节点的所有信息为：val[i]
其他节点信息为：val[find[i]]+val[i]
(因为前面先find压缩了，信息量都叠加回当前结点i了)

点击查看代码