本文共 499 字，大约阅读时间需要 1 分钟。

并查集解决球体连接问题

在球体连接问题中，常用的方法是并查集。通过并查集，将所有相交的球体合并为一条通路，并通过枚举判断底部球体与顶部球体之间是否存在通路。

并查集实现

并查集主要通过父指针数组par来管理集合的连通性。find函数用于查找集合的根节点，isConnected函数通过比较两个节点的根节点来判断是否连通。connect函数用于合并两个集合。

球体相交判断

通过计算两球体中心的距离平方dist，判断是否小于等于两球半径之和的平方4*r*r，从而确定两球体是否相交或相切。

底部与顶部球体分类

将球体分为底部球体（z - r <= 0）和顶部球体（z + r >= h）。

连接检查

使用并查集将底部球体与顶部球体进行连接检查，判断是否存在通路。如果存在通路，输出"Yes"；否则输出"No"。

代码实现细节

该方法通过并查集高效管理连通性，确保了算法的时间复杂度为O(n^2 * α(n))，适用于大规模数据。

转载地址：http://igrk.baihongyu.com/