給出一幅有向圖的邊的連接情況（edges數(shù)組包含n個(gè)值，edges[i]不等于-1表示存在從i到edges[i]的邊），節(jié)點(diǎn)編號o~n-1，給出node1，node2兩個(gè)節(jié)點(diǎn)問是否存在一個(gè)節(jié)點(diǎn)j，使得從node1到j(luò)和從node2到j(luò)的兩個(gè)距離中的較大值最小，輸出這個(gè)節(jié)點(diǎn)值，如果不存在，輸出-1
DFS分別預(yù)處理從node1和node2到每個(gè)其他節(jié)點(diǎn)的距離，因?yàn)樵瓐D有環(huán)，注意是否已經(jīng)訪問過（看dis數(shù)組是否已經(jīng)更新），然后枚舉所有節(jié)點(diǎn)，找出是否存在所求節(jié)點(diǎn)j
1 #2359
2 #Runtime: 1986 ms (Beats 26.67%)
3 #Memory: 115 MB (Beats 13.33%)
4
5 class Solution(object):
6 def closestMeetingNode(self, edges, node1, node2):
7 """
8 :type edges: List[int]
9 :type node1: int
10 :type node2: int
11 :rtype: int
12 """
13
14 def DFS(r, d, dis):
15 if r == -1 or dis[r] != -1:
16 return
17 dis[r] = d
18 DFS(edges[r], d + 1, dis)
19
20 n = len(edges)
21 dis1, dis2 = [-1] * n, [-1] * n
22 DFS(node1, 0, dis1)
23 DFS(node2, 0, dis2)
24 min_dis = 100001
25 ans = -1
26 for i in range(n):
27 if min(dis1[i], dis2[i]) >= 0 and max(dis1[i], dis2[i]) < min_dis:
28 min_dis = max(dis1[i], dis2[i])
29 ans = i
30 return ans