給出一個(gè)無(wú)向圖（給定節(jié)點(diǎn)數(shù)、所有的邊），問(wèn)是否存在連接起點(diǎn)到終點(diǎn)的路，簡(jiǎn)單DFS，用set記錄訪問(wèn)過(guò)的節(jié)點(diǎn)（改為記錄訪問(wèn)過(guò)的邊會(huì)TLE）
寫(xiě)法一，DFS完判定終點(diǎn)是否到達(dá)過(guò)
1 #1971
2 #Runtime: 3120 ms (Beats 67.40%)
3 #Memory: 348.8 MB (Beats 5.11%)
4
5 class Solution(object):
6 def validPath(self, n, edges, source, destination):
7 """
8 :type n: int
9 :type edges: List[List[int]]
10 :type source: int
11 :type destination: int
12 :rtype: bool
13 """
14 graph_dict = defaultdict(set)
15 vis = set()
16 for x, y in edges:
17 graph_dict[x].add(y)
18 graph_dict[y].add(x)
19
20 def DFS(t, des):
21 vis.add(t)
22 if t == des:
23 return
24 if t in graph_dict:
25 for j in graph_dict[t]:
26 if j not in vis:
27 DFS(j, des)
28 DFS(source, destination)
29 return destination in vis
寫(xiě)法二，DFS過(guò)程中直接判False或者True，不知為何此種寫(xiě)法慢一些
1 #1971
2 #Runtime: 4947 ms (Beats 17.28%)
3 #Memory: 353 MB (Beats 5.11%)
4
5 class Solution(object):
6 def validPath(self, n, edges, source, destination):
7 """
8 :type n: int
9 :type edges: List[List[int]]
10 :type source: int
11 :type destination: int
12 :rtype: bool
13 """
14 graph_dict = defaultdict(set)
15 vis = set()
16 for x, y in edges:
17 graph_dict[x].add(y)
18 graph_dict[y].add(x)
19
20 def DFS(t, des):
21 vis.add(t)
22 if t == des:
23 return True
24 if t in graph_dict:
25 for j in graph_dict[t]:
26 if j not in vis and DFS(j, des):
27 return True
28 return False
29 return DFS(source, destination)
30