給出一個(gè)無向圖（給定節(jié)點(diǎn)數(shù)、所有的邊），問是否存在連接起點(diǎn)到終點(diǎn)的路，簡單DFS，用set記錄訪問過的節(jié)點(diǎn)（改為記錄訪問過的邊會TLE）
寫法一，DFS完判定終點(diǎn)是否到達(dá)過
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
寫法二，DFS過程中直接判False或者True，不知為何此種寫法慢一些
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