算法打卡：第十一章 图论part05

今日收获：并查集理论基础，寻找存在的路径

1. 并查集理论基础（from代码随想录）

（1）应用场景：判断两个元素是否在同一个集合中

（2）原理讲解：通过一个一维数组，根存储的元素是自己，其他节点存储的元素是自己的上一级元素。在查找时，判断两个元素的根是否相同。

（3）路径压缩：让所有的其他节点都直接存储根节点，避免树的高度太深，递归次数太多

（4）主要功能：

• 寻找任意节点的根节点；
• 将两个节点加入同一个集合；
• 判断两个节点是否在同一个集合；

（5）常见误区：在添加节点时，必须先找到两个节点的根，然后将根相连。

2. 寻找存在的路径

题目链接：107. 寻找存在的路径

思路：将节点用并查集的方式存储，判断两节点是否存在路径就是看这两个节点的根节点是否相同

方法：

import java.util.Scanner;public class Main{public static void main(String[] args){Scanner sc=new Scanner(System.in);// 接收数据int N=sc.nextInt();int M=sc.nextInt();int[] tree=new int[N+1];// 初始化，每个节点都是根节点for (int i=1;i<N+1;i++){tree[i]=i;}// 添加节点for (int i=0;i<M;i++){int s=sc.nextInt();int t=sc.nextInt();int sRoot=find(tree,s);int tRoot=find(tree,t);tree[tRoot]=sRoot;}int source=sc.nextInt();int dest=sc.nextInt();int root1=find(tree,source);int root2=find(tree,dest);if (root1==root2){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;}}