Re: [閒聊] 每日LeetCode已回收
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：
----------------------------------------------
class Solution {
public boolean validPath(int n, int[][] edges, int source, int
destination) {
int[] root = new int[n];
for (int i = 0; i < n; i++) {
root[i] = i;
}
for (int[] edge : edges) {
union(root, edge[0], edge[1]);
}
return find(root, source) == find(root, destination);
}
private int find(int[] root, int x) {
return root[x] == x ? x : (root[x] = find(root, root[x]));
}
private void union(int[] root, int x, int y) {
root[find(root, x)] = root[find(root, y)];
}
}
----------------------------------------------
https://i.imgur.com/acHi4CL.png
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 36.231.28.50 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1671413330.A.CA5.html
推
12/19 09:59,
3年前
, 1F
12/19 09:59, 1F
→
12/19 11:46,
3年前
, 2F
12/19 11:46, 2F
討論串 (同標題文章)
完整討論串 (本文為第 142 之 719 篇)：