服务器如何架设网站,建设银行手机银行网站,高端前端开发,转换成wordpress一、什么是并查集
并查集的逻辑结构是一个包含N个元素的集合#xff0c;如图#xff1a; 我们将各个元素划分为若干个互不相交的子集#xff0c;如图#xff1a; 二、并查集的基本操作
#xff08;一#xff09;初始化
初始化可以先将每个子集指向自己 //初始化int []…一、什么是并查集
并查集的逻辑结构是一个包含N个元素的集合如图 我们将各个元素划分为若干个互不相交的子集如图 二、并查集的基本操作
一初始化
初始化可以先将每个子集指向自己 //初始化int [] unnew int[10];for (int i 0; i un.length; i) { //先使得每个子集指向子集un[i]i;}二Find操作
返回指定索引的根
//并查集查询public int find(int x){if (un[x]x){ //如果当前并查集指向自己 那么直接返回当前值即可return x;}else { //如果不指向自己 则代表有可能有指向链 那么就递归寻找 直到找到最终的根节点return find(un[x]);}} 三Union操作 ●合并操作即将一个根指向另一个指定节点
//合并 也就是使得i指向jpublic void merge(int i,int j){un[find(i)]find(j); // un[find(i)] 是指 如果i索引 有指向其他节点的话 那么肯定要遍历到最终指向的父节点 然后将父节点与指定索引值合并 没有指向的话那么就是直接使得当前位置i指向j}
四Union操作路径压缩 //合并压缩路径public int union(int x){if (un[x]x){ //代表此时已经是跟节点return x;}else {un[x]union(un[x]); //使得每一个节点都指向该父节点 比如1—2—3 3是最终根节点 那么这样写的最终效果就是 1-3 2—3 3-3return un[x]; //返回父节点}}
