Java实现并查集
本文实例为大家分享了Java实现并查集的具体代码,供大家参考,具体内容如下
自下而上的树结构
接口
/** * @author Nino */public interface UF { int size(); /** * 看两个元素是否相连 * @param p * @param q * @return */ boolean isConnected(int p, int q); /** * 将两个元素合并在一起,变成一个集合中的元素 * @param p * @param q */ void unionElements(int p, int q);}
使用路径压缩的并查集
/** * @author Nino */public class UnionFind5 implements UF { private int[] parent; //rank[i]表示以i为根的集合中树的层数 private int[] rank; public UnionFind5(int size) { parent = new int[size]; rank = new int[size]; for (int i = 0; i < size; i++) { parent[i] = i; rank[i] = 1; } } @Override public int size() { return parent.length; } /** * 查找过程,查找元素p所对应的集合编号 * O(h)复杂度,h为树的高度 * 使用路径压缩 * @param p * @return */ private int find(int p) { if (p < 0 && p >= parent.length) { throw new IllegalArgumentException('p is illegal'); } if (p != parent[p]) { parent[p] = find(parent[p]); } return parent[p]; } /** * 查询p, q是否同属一个集合 * 时间复杂度O(h) * @param p * @param q * @return */ @Override public boolean isConnected(int p, int q) { return find(p) == find(q); } /** * 合并元素p, q所属的集合,只需要把Rank低的根节点指向Rank高的根节点就可以 * O(h)复杂度 * @param p * @param q */ @Override public void unionElements(int p, int q) { int pRoot = find(p); int qRoot = find(q); if (pRoot == qRoot) { return; } //败者食尘 if (rank[pRoot] < rank[qRoot]) { parent[pRoot] = qRoot; } else if (rank[qRoot] < rank[pRoot]) { parent[qRoot] = pRoot; } else { parent[qRoot] = pRoot; rank[pRoot] += 1; } }}
以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持好吧啦网。
相关文章:
1. 将properties文件的配置设置为整个Web应用的全局变量实现方法2. ASP.NET MVC使用异步Action的方法3. 在Asp.net core项目中使用WebSocket4. JavaScript实现组件化和模块化方法详解5. Python制作一个随机抽奖小工具的实现6. 使用python画出逻辑斯蒂映射(logistic map)中的分叉图案例7. 利用FastReport传递图片参数在报表上展示签名信息的实现方法8. SpringMVC+Jquery实现Ajax功能9. python3.8.1+selenium实现登录滑块验证功能10. matplotlib如何设置坐标轴刻度的个数及标签的方法总结