→ DJYOSHITAKA: 別捲了 04/21 14:27
推 SecondRun: 大師 04/21 16:34
※ 引述《Rushia (早瀬ユウカの体操服 )》之銘言：
: 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)
: -------------------------------------------
思路:
建圖 然後dfs
class Solution:
def validPath(self, n: int, edges: List[List[int]], source: int,
destination: int) -> bool:
dic = {}
visited = set()
for x,y in edges:
if x in dic:
dic[x].append(y)
else:
dic[x] = [y]
if y in dic:
dic[y].append(x)
else:
dic[y] = [x]
def dfs(start):
if start == destination:
return True
visited.add(start)
for node in dic[start]:
if node not in visited:
if dfs(node):
return True
return False
return dfs(source)
寫得有夠醜 並查集感覺更好
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 114.43.137.148 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1713680522.A.59F.html