给出一个无向图（给定节点数、所有的边），问是否存在连接起点到终点的路，简单DFS，用set记录访问过的节点（改为记录访问过的边会TLE）
写法一，DFS完判定终点是否到达过
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