代码随想录算法训练营第五十四天 | 并查集理论基础、Carl107-寻找存在的路径
并查集理论基础
文章讲解：https://www.programmercarl.com/kamacoder/图论并查集理论基础.html
视频讲解：https://www.bilibili.com/video/BV1pFjUzvES2
并查集常用来解决连通性问题，就是当我们需要判断两个元素是否在同一个集合里的时候，我们就要想到用并查集
并查集主要有两个功能：将两个元素添加到一个集合中、判断两个元素在不在同一个集合
我们将三个元素A，B，C （分别是数字）放在同一个集合，其实就是将三个元素连通在一起。用一个一维数组来表示连通，即：father[A] = B，father[B] = C，这样就表述 A 与 B 与 C连通了（有向连通图）
// 将v, u这条边加入并查集
void join(int u, int v){u = find(u); // 寻找u的根v = find(v); // 寻找v的根if(u == v) return; // 如果根相同，则说明v和u已经在同一集合，无需重复加入father[v] = u;
}
判断这三个元素是否在同一个集合里需要寻根思路，只要 A ，B，C 在同一个根下就是在同一个集合。给出A元素，就可以通过 father[A] = B，father[B] = C，找到A的根为 C；给出B元素，就可以通过 father[B] = C，找到B的根也为 C，说明 A 和 B 是在同一个集合里
// 并查集寻根过程
void find(int u){if(father[u] == u) return u; // 如果自己就是根，则直接返回自己return find(father[u]); // 如果根不是自己，就继续往下递归找根
}
如何表示 C 也在同一个集合里呢？需要 father[C] = C，即C的根也为C，这样就方便表示 A，B，C 都在同一个集合里了。也是因为这样，father数组初始化的时候要father[i] = i，默认自己的根指向自己
// 并查集初始化
void init(){for(int i = 0; i < nodeNum; i++){father[i] = i;}
}
如何判断两个元素是否在同一个集合里？如果通过find函数找到两个元素属于同一个根的话，那么这两个元素就在同一个集合
// 判断u和v是否找到同一个根
boolean isSame(int u, int v){u = find(u);v = find(v);return u == v;
}
另外，在实现find函数的过程中，通过递归的方式不断获取father数组下标对应的数值以此来找到这个集合的根，搜索过程像是从一个多叉树的叶子找到根节点的过程。如果这棵多叉树高度很深，每次find函数去寻找根的过程就要递归很多次
我们的目的只需要知道这些节点在同一个根下，所以可以将这颗多叉树改造，除了根节点，其他所有节点都挂载在根节点下，保持一层，这样寻根的时候就可以很快，由此要进行路径压缩，将非根节点的所有节点直接指向根节点。如何在代码层面实现呢？其实只需要在find函数递归的过程中，用father[u]去接收传过来的根节点find(father[u])即可
int find(int u){if(father[u] == u) return u;father[u] = find(father[u]);return father[u];
}
综上，便有了一份代码模板
void init(){for(int i = 0; i < nodeNum; i++){father[i] = i;}
}int find(int u){if(father[u] == u) return u;father[u] = find(father[u]);return father[u];
}void join(int u, int v){u = find(u);v = find(v);if(u == v) return;father[u] = v;
}boolean isSame(int u, int v){u = find(u);v = find(v);return u == v;
}
Carl107 寻找存在的路径
题目链接：https://kamacoder.com/problempage.php?pid=1179
文章讲解：https://www.programmercarl.com/kamacoder/0107.寻找存在的路径.html
视频讲解：https://www.bilibili.com/video/BV1k3T7zWEVj
并查集基础题目，并查集解决的主要是集合问题：两个节点在不在一个集合、两个节点添加到一个集合中
import java.util.*;public class Main{static int nodeNum = 0;static int edgeNum = 0;public static void initFather(int[] father){for(int i = 1; i <= nodeNum; i++){father[i] = i;}}public static int find(int[] father, int x){if(father[x] == x) return x;father[x] = find(father, father[x]);return father[x];}public static void join(int[] father, int a, int b){a = find(father, a);b = find(father, b);if(a == b) return;father[a] = b;}public static boolean judgeIsSame(int[] father, int a, int b){a = find(father, a);b = find(father, b);if(a == b) return true;return false;}public static void main(String[] args){Scanner scan = new Scanner(System.in);nodeNum = scan.nextInt();edgeNum = scan.nextInt();int[] father = new int[nodeNum+1];initFather(father);for(int i = 0; i < edgeNum; i++){int s = scan.nextInt();int t = scan.nextInt();join(father, s, t);}int source = scan.nextInt();int destination = scan.nextInt();if(judgeIsSame(father, source, destination)){System.out.println(1);}else{System.out.println(0);}}
}