Re: [闲聊] 每日LeetCode

楼主: Rushia (みけねこ的鼻屎)   2022-12-19 09:28:47
1971. Find if Path Exists in Graph
给你一堆边,判断其中的两个点是否连通。
Example:
https://assets.leetcode.com/uploads/2021/08/14/validpath-ex1.png
Input: n = 3, edges = [[0,1],[1,2],[2,0]], source = 0, destination = 2
Output: true
Explanation: There are two paths from vertex 0 to vertex 2:
- 0 → 1 → 2
- 0 → 2
https://assets.leetcode.com/uploads/2021/08/14/validpath-ex2.png
Input: n = 6, edges = [[0,1],[0,2],[3,5],[5,4],[4,3]], source = 0,
destination = 5
Output: false
Explanation: There is no path from vertex 0 to vertex 5.
思路:
1.检查图形是否连通可以用并查集,先初始化每个点的群组再依据边来把所有
的点都union起来。
2.最后检查source和destination是不是在同一个群组即可。
Java Code:
作者: pandix (面包屌)   2022-12-19 09:59:00
大师
作者: DDFox (冒险者兼清洁工)   2022-12-19 11:46:00
大师

Links booklink

Contact Us: admin [ a t ] ucptt.com