中医院网站模板,编辑网页的工具有哪些,跨国网站,网络营销国外研究现状今日收获#xff1a;并查集理论基础#xff0c;寻找存在的路径
1. 并查集理论基础#xff08;from代码随想录#xff09;
#xff08;1#xff09;应用场景#xff1a;判断两个元素是否在同一个集合中
#xff08;2#xff09;原理讲解#xff1a;通过一个一维数组…今日收获并查集理论基础寻找存在的路径
1. 并查集理论基础from代码随想录
1应用场景判断两个元素是否在同一个集合中
2原理讲解通过一个一维数组根存储的元素是自己其他节点存储的元素是自己的上一级元素。在查找时判断两个元素的根是否相同。
3路径压缩让所有的其他节点都直接存储根节点避免树的高度太深递归次数太多
4主要功能
寻找任意节点的根节点将两个节点加入同一个集合判断两个节点是否在同一个集合
5常见误区在添加节点时必须先找到两个节点的根然后将根相连。
2. 寻找存在的路径
题目链接107. 寻找存在的路径
思路将节点用并查集的方式存储判断两节点是否存在路径就是看这两个节点的根节点是否相同
方法
import java.util.Scanner;public class Main{public static void main(String[] args){Scanner scnew Scanner(System.in);// 接收数据int Nsc.nextInt();int Msc.nextInt();int[] treenew int[N1];// 初始化每个节点都是根节点for (int i1;iN1;i){tree[i]i;}// 添加节点for (int i0;iM;i){int ssc.nextInt();int tsc.nextInt();int sRootfind(tree,s);int tRootfind(tree,t);tree[tRoot]sRoot;}int sourcesc.nextInt();int destsc.nextInt();int root1find(tree,source);int root2find(tree,dest);if (root1root2){System.out.println(1);}else {System.out.println(0);} }// 寻找根节点public static int find(int[] tree, int node){if (tree[node]node){ // 根节点return node;}return tree[node]find(tree,tree[node]);}
}
3. 并查集Java模板
主要的方法寻找根节点加入并查集判断是否连接
//并查集模板
class DisJoint{private int[] father;public DisJoint(int N) {father new int[N];for (int i 0; i N; i){father[i] i;}}public int find(int n) {return n father[n] ? n : (father[n] find(father[n]));}public void join (int n, int m) {n find(n);m find(m);if (n m) return;father[m] n;}public boolean isSame(int n, int m){n find(n);m find(m);return n m;}}
