Day48 | 107.寻找存在的路径

本文主要是介绍Day48 | 107.寻找存在的路径，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

语言

Java

107.寻找存在的路径

题目

107. 寻找存在的路径

题目描述

给定一个包含 n 个节点的无向图中，节点编号从 1 到 n （含 1 和 n ）。

你的任务是判断是否有一条从节点 source 出发到节点 destination 的路径存在。

输入描述

第一行包含两个正整数 N 和 M，N 代表节点的个数，M 代表边的个数。 

后续 M 行，每行两个正整数 s 和 t，代表从节点 s 与节点 t 之间有一条边。 

最后一行包含两个正整数，代表起始节点 source 和目标节点 destination。

输出描述

输出一个整数，代表是否存在从节点 source 到节点 destination 的路径。如果存在，输出 1；否则，输出 0。

思路

1. 初始化并查集：
   • 创建一个大小为n+1的数组father，其中n是节点的数量。每个位置i的值初始化为i，表示每个节点最初都是自己的根节点。
2. 处理边的连接：
   • 读入每条边的两个端点s和t，然后调用join(s, t)方法来合并这两个节点所在的集合。
3. 判断连通性：
   • 对于给定的源节点source和目标节点destination，分别找到它们各自的根节点，如果这两个根节点相同，则表示这两个节点是连通的。

代码

import java.util.Scanner;
import java.util.Arrays;public class Main {private static int n; // Number of nodesprivate static int[] father; // Parent array initialized to store parent for each nodepublic static void main(String[] args) {Scanner scanner = new Scanner(System.in);n = scanner.nextInt(); // Read the number of nodesint m = scanner.nextInt(); // Read the number of edgesinit(n); // Initialize the union-find data structurewhile (m-- > 0) {int s = scanner.nextInt();int t = scanner.nextInt();join(s, t); // Join the two nodes}int source = scanner.nextInt();int destination = scanner.nextInt();System.out.println(isSame(source, destination) ? 1 : 0); // Check if source and destination are in the same setscanner.close();}// Initializes the parent array with the nodes themselvesprivate static void init(int n) {father = new int[n + 1];Arrays.fill(father, -1); // Initialize all parents to -1for (int i = 1; i <= n; i++) {father[i] = i; // Each node is its own parent initially}}// Finds the root of the set that contains node 'u'private static int find(int u) {return u == father[u] ? u : (father[u] = find(father[u])); // Path compression}// Checks if nodes 'u' and 'v' belong to the same setprivate static boolean isSame(int u, int v) {return find(u) == find(v);}// Merges the sets containing nodes 'u' and 'v'private static void join(int u, int v) {u = find(u); // Find the root of the set containing uv = find(v); // Find the root of the set containing vif (u == v) return; // If they are already in the same set, do nothingfather[v] = u; // Make the root of v point to the root of u}
}

易错点

1. 初始化时的赋值：

   • 在初始化时，每个节点的父节点应被设为它自己。在Java中，可以先使用Arrays.fill(father, -1)将数组填充为-1，然后再遍历数组将每个位置设为它自己。这样做是为了避免负数作为节点编号的情况。

2. 路径压缩：

   • 在find方法中，使用了路径压缩技术，即在递归查找根节点的过程中更新每个节点的父节点，使其直接指向根节点。这样可以提高查找效率。

3. 循环条件：

   • 在处理边的循环中，使用while (m-- > 0)，这里m--意味着每次循环后m的值减1。这是一个常见的写法，但需要注意不要在循环外部再对m进行操作，否则可能会导致逻辑错误。

4. 边界情况：

   • 在join方法中，如果两个节点已经是同一个集合中的成员，则不需要做任何操作。这可以通过检查两个节点的根节点是否相同来实现。

总结

今天学了并查集理论

应用完成了一道题

明天继续图论继续加油！

天道酬勤

这篇关于Day48 | 107.寻找存在的路径的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---