推 digua: 大師 04/21 12:53
推 oinishere: 大師 04/21 13:09
https://leetcode.com/problems/find-if-path-exists-in-graph/description
1971. Find if Path Exists in Graph
給你一個陣列表示的圖，判斷 source 和 destination 是否連通。
思路:
1.把所有邊的點加到併查集，然後查這兩點有沒有連通就好。
py code:
-------------------------------------------
class Solution:
def validPath(self, n: int, edges: List[List[int]], source: int,
destination: int) -> bool:
root = [x for x in range(n)]
def find(x):
if x != root[x]:
root[x] = find(root[x])
return root[x]
for edge in edges:
x = find(edge[0])
y = find(edge[1])
root[x] = y
return find(source) == find(destination)
-------------------------------------------
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 122.100.73.13 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1713674679.A.F13.html
※ 編輯: Rushia (122.100.73.13 臺灣), 04/21/2024 12:49:56