Day55–图论–107. 寻找存在的路径（卡码网）
今天学习并查集。先过一遍并查集理论基础。再做下面这一道模板题，就可以结束了。体量不多，但是理解并查集，并使用好，不容易。
后续再找相关的题目来做，更新在下方。
107. 寻找存在的路径（卡码网）
方法：并查集
思路：
建立并查集类，完成isSame，find和join三个方法。
import java.util.*;public class Main {public static void main(String[] args) {Scanner in = new Scanner(System.in);int n = in.nextInt();int m = in.nextInt();Disjoint dj = new Disjoint(n);for (int i = 0; i < m; i++) {int from = in.nextInt();int to = in.nextInt();dj.join(from, to);}int source = in.nextInt();int destination = in.nextInt();if (dj.isSame(source, destination)) {System.out.println(1);} else {System.out.println(0);}}
}class Disjoint {private int[] father;public Disjoint(int n) {father = new int[n + 1];for (int i = 0; i <= n; i++) {father[i] = i;}}public void join(int a, int b) {int root1 = find(a);int root2 = find(b);if (root1 == root2) {return;}father[root2] = root1;}public boolean isSame(int a, int b) {int root1 = find(a);int root2 = find(b);return root1 == root2;}public int find(int a) {if (a == father[a]) {return a;} else {// return find(father[a]);return father[a] = find(father[a]);}}
}推荐题目
来自@灵艾山茶府：常用数据结构（前缀和/差分/栈/队列/堆/字典树/并查集/树状数组/线段树）链接中可以搜到并查集相关题目。实际上，可以用并查集做的题目，用其他方法也可以做。
：专注于异步操作延的C++开源库 continuable)
)
详解)
