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)
)
詳解)
