107. 寻找存在的路径

题目描述给定一个包含 n 个节点的无向图中节点编号从 1 到 n 含 1 和 n 。你的任务是判断是否有一条从节点 source 出发到节点 destination 的路径存在。输入描述第一行包含两个正整数 N 和 MN 代表节点的个数M 代表边的个数。后续 M 行每行两个正整数 s 和 t代表从节点 s 与节点 t 之间有一条边。最后一行包含两个正整数代表起始节点 source 和目标节点 destination。输出描述输出一个整数代表是否存在从节点 source 到节点 destination 的路径。如果存在输出 1否则输出 0。输入示例5 4 1 2 1 3 2 4 3 4 1 4输出示例1import java.util.*; public class Main{ public static void main(String[] args) { int N, M; Scanner scanner new Scanner(System.in); N scanner.nextInt(); M scanner.nextInt(); DisJoint disJoint new DisJoint(N 1); for (int i 0; i M; i) { disJoint.join(scanner.nextInt(), scanner.nextInt()); } if(disJoint.isSame(scanner.nextInt(), scanner.nextInt())) { System.out.println(1); } else { System.out.println(0); } } } //并查集模板 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; } }