Re: [閒聊] 每日LeetCode

[Rushia (みけねこ的鼻屎)]

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

--
https://i.imgur.com/PIoxddO.jpg

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 36.231.28.50 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1671413330.A.CA5.html
推 pandix: 大師
→ DDFox: 大師