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